図の右上のshowボタンを押すとRのコードが表示されます。

4.1 三つ以上の変数の可視化

4.1.1 レーダーチャートの印象

Rでレーダーチャートを描くパッケージはいくつかあるのだが、どれもイマイチ納得いかなかったのでポーラーチャートで勘弁して下さい。

中澤先生から教えていただいたfmsbパッケージを使う方法でキレイに描けました!

fmsbパッケージの日本語マニュアルはこちら

library(conflicted)
library(tidyverse)
## ── Attaching core tidyverse packages ──────────────────────── tidyverse 2.0.0 ──
## ✔ dplyr     1.1.4     ✔ readr     2.1.4
## ✔ forcats   1.0.0     ✔ stringr   1.5.1
## ✔ ggplot2   3.4.4     ✔ tibble    3.2.1
## ✔ lubridate 1.9.3     ✔ tidyr     1.3.0
## ✔ purrr     1.0.2
library(fmsb)

data1 <- data.frame(
  国語 = c(5, 1, 5, 3),
  理科 = c(5, 1, 5, 4),
  社会 = c(5, 1, 4, 3),
  体育 = c(5, 1, 4, 4),
  音楽 = c(5, 1, 5, 2),
  数学 = c(5, 1, 5, 2)
  )

data2 <- data.frame(
  数学 = c(5, 1, 5, 5),
  国語 = c(5, 1, 5, 1),
  理科 = c(5, 1, 1, 5),
  社会 = c(5, 1, 1, 1),
  体育 = c(5, 1, 1, 5),
  音楽 = c(5, 1, 5, 1)
  )

par(mfrow = c(2, 2), oma = c(0,0,0,0), mar = c(0,0,0,0))
# plot1
data1 |>
  select(数学, 国語, 理科, 社会, 体育, 音楽) |>
  radarchart(
    axistype = 4, seg = 4, pty = 32, pcol = c(4, 2),
    pfcol = c(adjustcolor("lightblue", 0.5), adjustcolor("pink", 0.5)),
    caxislabels=sprintf("%d", 1:5)
    ) 
text(-0.4, -0.3,  "Aさん", col="red")
text(-0.4, 0.6,"Bさん", col="blue")

# plot2
data1 |>
  select(音楽, 数学, 理科, 体育, 社会, 国語) |>
  radarchart(
    axistype = 4, seg = 4, pty = 32, pcol = c(4, 2),
    pfcol = c(adjustcolor("lightblue", 0.5), adjustcolor("pink", 0.5)),
    caxislabels=sprintf("%d", 1:5)
    ) 
text(-0.4, -0.3, "Aさん", col="red")
text(-0.4, 0.6, "Bさん", col="blue")

# plot3
data2 |>
  select(数学, 国語, 理科, 社会, 体育, 音楽) |>
  radarchart(
    axistype = 4, seg = 4, pty = 32, pcol = c(4, 2),
    pfcol = c(adjustcolor("lightblue", 0.5), adjustcolor("pink", 0.5)),
    caxislabels=sprintf("%d", 1:5)
    ) 
text(-0.4, -0.3, "Aさん", col="red")
text(-0.4, 0.6, "Bさん", col="blue")

# plot4
data2 |>
  select(音楽, 数学, 理科, 体育, 社会, 国語) |>
  radarchart(
    axistype = 4, seg = 4, pty = 32, pcol = c(4, 2),
    pfcol = c(adjustcolor("lightblue", 0.5), adjustcolor("pink", 0.5)),
    caxislabels=sprintf("%d", 1:5)
    ) 
text(-0.4, -0.3, "Aさん", col="red")
text(-0.4, 0.6, "Bさん", col="blue")

par(mfrow = c(1, 1))
library(conflicted)
library(tidyverse)
library(patchwork)

data1 <- data.frame(
  person = c("Aさん", "Bさん"), 
  数学 = c(5, 2),
  国語 = c(5, 3),
  理科 = c(5, 4),
  社会 = c(4, 3),
  体育 = c(4, 4),
  音楽 = c(5, 2)
  ) |>
  pivot_longer(!person)

# compelling data
data2 <- data.frame(
  person = c('Aさん', 'Bさん'),
  数学 = c(5, 5),
  国語 = c(5, 1),
  理科 = c(1, 5),
  社会 = c(1, 1),
  体育 = c(1, 5),
  音楽 = c(5, 1)
) |>
  pivot_longer(!person)

# 並び1
p1 <- data1 |>
  mutate(name = factor(name, levels = c("数学", "国語", "理科", "社会", "体育", "音楽"))) |>
  ggplot(aes(x = name, y = value, fill = person, group = person)) +
  geom_col(position = position_dodge(width=1)) +
  coord_polar() +
    theme(
      legend.position="none", 
      axis.title.x=element_blank(), 
      axis.title.y=element_blank()
    )

# 並び2
p2 <- data1 |>
  mutate(name = factor(name, levels = c("音楽", "数学", "理科", "体育", "社会", "国語"))) |>
  ggplot(aes(x = name, y = value, fill = person, group = person)) +
  geom_col(position = position_dodge(width=1)) +
  coord_polar() +
    theme(
      legend.position="none", 
      axis.title.x=element_blank(), 
      axis.title.y=element_blank()
    )

# 並び1
p3 <- data2 |>
  mutate(name = factor(name, levels = c("数学", "国語", "理科", "社会", "体育", "音楽"))) |>
  ggplot(aes(x = name, y = value, fill = person, group = person)) +
  geom_col(position = position_dodge(width=1)) +
  coord_polar() +
    theme(
      legend.position="none", 
      axis.title.x=element_blank(), 
      axis.title.y=element_blank()
    )

# 並び2
p4 <- data2 |>
  mutate(name = factor(name, levels = c("音楽", "数学", "理科", "体育", "社会", "国語"))) |>
  ggplot(aes(x = name, y = value, fill = person, group = person)) +
  geom_col(position = position_dodge(width=1)) +
  coord_polar() +
    theme(
      legend.position="none", 
      axis.title.x=element_blank(), 
      axis.title.y=element_blank()
    )

(p1 + p2) / (p3 + p4)

4.1.2 各変数の特徴を概観して比較する

library(conflicted)
library(tidyverse)
library(patchwork)

v_names <- c(
    "ブドウの品種", "アルコール度数", "リンゴ酸", "ミネラル分", 
    "ミネラル分のアルカリ度", "マグネシウム", "全フェノール類", "フラバノイド",
    "非フラバノイドフェノール類", "プロアントシアニン", "色の強さ", "色相",
    "OD280/OD315値", "プロリン"
  )

df <- read_csv(
  "https://archive.ics.uci.edu/ml/machine-learning-databases/wine/wine.data",
  col_names = v_names,
  col_types = "f"
  ) |>
  mutate(across(where(is.numeric), \(x) scale(x))) |> #標準化
  rowid_to_column() |>
  pivot_longer(!c(ブドウの品種, rowid)) |>
  mutate(name = factor(name, levels = v_names))

df |>
  ggplot(aes(x = name, y = value, colour = ブドウの品種, group =rowid)) +
  geom_line(alpha = 0.5) +
  coord_flip() +
  labs(title = "ワインの特徴とブドウの品種", y = "相対スコア", x = "")

4.1.3 変数ごとに個別に可視化する方法

library(conflicted)
library(tidyverse)

v_names <- c(
    "ブドウの品種", "アルコール度数", "リンゴ酸", "ミネラル分", 
    "ミネラル分のアルカリ度", "マグネシウム", "全フェノール類", "フラバノイド",
    "非フラバノイドフェノール類", "プロアントシアニン", "色の強さ", "色相",
    "OD280/OD315値", "プロリン"
  )

df <- read_csv(
  "https://archive.ics.uci.edu/ml/machine-learning-databases/wine/wine.data",
  col_names = v_names,
  col_types = "f"
) |>
  mutate(across(where(is.numeric), \(x) scale(x))) |> #標準化
  rowid_to_column() |>
  pivot_longer(!c(ブドウの品種, rowid)) |>
  mutate(name = factor(name, levels = v_names))

p1 <- df |>
  ggplot(aes(x = name, y = value, group = ブドウの品種, fill = ブドウの品種)) +
  stat_summary(geom = "bar", fun = "mean", position = "dodge2") +
  stat_summary(geom = "errorbar", fun.data = "mean_se", position = "dodge2") +
  labs(y = "相対スコア", x = "") +
  theme(axis.text.x = element_text(angle = 45, hjust = 1),
        aspect.ratio = 3/4,
        legend.position = "none")

p2 <- df |>
  ggplot(aes(x = name, y = value, fill = ブドウの品種)) +
  geom_violin(position="dodge") +
  labs(y = "相対スコア", x = "") +
  theme(axis.text.x = element_text(angle = 45, hjust = 1),
        aspect.ratio = 3/4,
        legend.position = "none")

p1 / p2

4.1.4 ヒートマップ

library(conflicted)
library(tidyverse)

v_names <- c(
    "ブドウの品種", "アルコール度数", "リンゴ酸", "ミネラル分", 
    "ミネラル分のアルカリ度", "マグネシウム", "全フェノール類", "フラバノイド",
    "非フラバノイドフェノール類", "プロアントシアニン", "色の強さ", "色相",
    "OD280/OD315値", "プロリン"
  )

df <- read_csv(
  "https://archive.ics.uci.edu/ml/machine-learning-databases/wine/wine.data",
  col_names = v_names,
  col_types = "f"
  ) |>
  mutate(across(where(is.numeric), \(x) scale(x))) |> #標準化
  rowid_to_column() |>
  pivot_longer(!c(rowid, ブドウの品種)) |>
  mutate(name = factor(name, levels = rev(v_names)))

jet.colors <- colorRampPalette(c("#00007F", "blue", "#007FFF", "cyan", "#7FFF7F", "yellow", "#FF7F00", "red", "#7F0000"))

df |>
  ggplot(aes(x = rowid, y = name, fill = value)) +
  geom_tile() +
  facet_wrap(vars(ブドウの品種), scales = "free_x") + 
  scale_fill_gradientn(colours = jet.colors(100)) +
  labs(x = "ワイン銘柄番号", y = "", title = "カラーコードで値を表現する")

4.1.5 各個体の行動時系列を可視化する

library(conflicted)
library(tidyverse)

df <- read_csv(
  "https://raw.githubusercontent.com/tkEzaki/data_visualization/main/4%E7%AB%A0/data/behavior_data.csv"
  ) |>
  mutate(Time = Time / 3600)  |> # Time列を秒から時間に変換
  pivot_longer(!Time) |>
  mutate(
    value = case_when(
      value == "Garbage" ~ "ゴミ捨て場",
      value == "Nest" ~ "寝室",
      value == "Other" ~ "一般の部屋",
      value == "Toilet" ~ "トイレ"
      ) |>
      factor(levels = c("ゴミ捨て場", "トイレ", "寝室", "一般の部屋"))
    ) 

df |>
  ggplot(aes(x =name , y = Time, fill = value)) +
  geom_tile() +
  scale_y_reverse() +
  scale_fill_brewer(palette = "Set1") +
  labs(title = "ヒートマップによる行動時系列の可視化", x = "個体", y = "時間[h]")

4.1.6 1個体の各行動の可視化

library(conflicted)
library(tidyverse)
library(patchwork)

# CSVデータを読み込む
df <- read_csv(
  "https://raw.githubusercontent.com/tkEzaki/data_visualization/main/4%E7%AB%A0/data/behavior_data.csv"
) |>
  mutate(Time = Time / 3600)  |> # Time列を秒から時間に変換
  pivot_longer(!Time) |>
  mutate(
    value = case_when(
      value == "Garbage" ~ "ゴミ捨て場",
      value == "Nest" ~ "寝室",
      value == "Other" ~ "一般の部屋",
      value == "Toilet" ~ "トイレ"
    ) |>
      factor(levels = rev(c("ゴミ捨て場", "トイレ", "寝室", "一般の部屋")))
  )

# 1個体(J)のデータ
df_j <- df |>
  dplyr::filter(name == "J") |> 
  dplyr::select(!name) |>
  mutate(action = "1")

p1 <- df_j |>
  ggplot(aes(x = value, y = Time, fill = value)) +
  geom_tile() +
  scale_y_reverse() +
  labs(x = "", y = "時間[h]") +
  scale_fill_brewer(palette = "Set1") +
  theme(
    legend.position="none",
    aspect.ratio = 4 / 1.5
    )

p2 <- df_j |>
  dplyr::filter(Time >= 13, Time <= 16) |>
  ggplot(aes(x = value, y = Time, fill = value)) +
  geom_tile() +
  scale_y_reverse() +
  labs(x = "", y = "時間[h]") +
  scale_fill_brewer(palette = "Set1") +
  theme(
    legend.position="none",
    aspect.ratio = 4 / 1.5
  )

p1 + p2

4.2.1 関係データのヒートマップによる可視化

library(conflicted)
library(tidyverse) 
library(patchwork)

# 共著データ
researchers <- c("A", "B", "C", "D", "E", "F", "G", "H", "I", "J")
collaboration <- matrix(
  c(
    NA, 1, 1, 0, 0, 0, 0, 0, 0, 1,
    1, NA, 0, 1, 1, 1, 0, 0, 0, 1,
    1, 0, NA, 0, 0, 0, 1, 1, 1, 0,
    0, 1, 0, NA, 0, 0, 0, 0, 0, 0,
    0, 1, 0, 0, NA, 0, 0, 0, 0, 0,
    0, 1, 0, 0, 0, NA, 0, 0, 0, 0,
    0, 0, 1, 0, 0, 0, NA, 0, 0, 0,
    0, 0, 1, 0, 0, 0, 0, NA, 0, 0,
    0, 0, 1, 0, 0, 0, 0, 0, NA, 0,
    1, 1, 0, 0, 0, 0, 0, 0, 0, NA
    ),
  nrow=10,
  dimnames = list(researchers, researchers)
  )

p1 <- collaboration |>
  as.data.frame() |>
  rownames_to_column() |>
  pivot_longer(!rowname) |>
  mutate(
    value = factor(value),
    name = factor(name, levels = rev(LETTERS[1:10]))
    ) |>
  ggplot(aes(x = rowname, y = name, fill = value, label = value)) +
  geom_tile() +
  geom_text() +
  scale_fill_hue(name = "", labels = c("0" = "共著なし", "1" ="共著あり")) +
  labs(title = "共著関係の有無", x = "", y = "") +
  theme(aspect.ratio = 1)

# ここはもうちょっとスマートに書けないか?
set.seed(0)
v0 <- runif(n = (100 -10)/2, min = 0.0, max = 0.5) |> round(2)
v1 <- runif(n = (100 -10)/2, min = 0.5, max = 1.0) |> round(2)
collaboration_score <- collaboration
collaboration_score[upper.tri(collaboration_score)] <-
  if_else(collaboration[lower.tri(collaboration)]== 1, v1, v0) 
collaboration_score <- t(collaboration_score)
collaboration_score[upper.tri(collaboration_score)] <-
  if_else(collaboration[lower.tri(collaboration)]== 1, v1, v0)

jet.colors <- colorRampPalette(c("#00007F", "blue", "#007FFF", "cyan", "#7FFF7F", "yellow", "#FF7F00", "red", "#7F0000"))

p2 <- collaboration_score |>
  as.data.frame() |>
  rownames_to_column() |>
  pivot_longer(!rowname) |>
  mutate(name = factor(name, levels = rev(LETTERS[1:10]))) |>
  ggplot(aes(x = rowname, y = name, fill = value, label = value)) +
  geom_tile() +
  geom_text(size = 2) +
  labs(title = "研究の興味の類似度", x = "", y = "") +
  theme(aspect.ratio = 1) +
  scale_fill_gradientn(colours = jet.colors(100))

p1 + p2

4.2.2 ネットワークによる関係データの可視化

ここはggraphで書き直すか?

library(conflicted)
library(tidyverse)
library(igraph)

# 共著データ
researchers <- c("A", "B", "C", "D", "E", "F", "G", "H", "I", "J")
collaboration <- matrix(
  c(
    NA, 1, 1, 0, 0, 0, 0, 0, 0, 1,
    1, NA, 0, 1, 1, 1, 0, 0, 0, 1,
    1, 0, NA, 0, 0, 0, 1, 1, 1, 0,
    0, 1, 0, NA, 0, 0, 0, 0, 0, 0,
    0, 1, 0, 0, NA, 0, 0, 0, 0, 0,
    0, 1, 0, 0, 0, NA, 0, 0, 0, 0,
    0, 0, 1, 0, 0, 0, NA, 0, 0, 0,
    0, 0, 1, 0, 0, 0, 0, NA, 0, 0,
    0, 0, 1, 0, 0, 0, 0, 0, NA, 0,
    1, 1, 0, 0, 0, 0, 0, 0, 0, NA
  ),
  nrow=10,
  dimnames = list(researchers, researchers)
)

# 研究の興味の類似度
set.seed(0)
v0 <- runif(n = (100 -10)/2, min = 0.0, max = 0.5) |> round(2)
v1 <- runif(n = (100 -10)/2, min = 0.5, max = 1.0) |> round(2)
collaboration_score <- collaboration
collaboration_score[upper.tri(collaboration_score)] <-
  if_else(collaboration[lower.tri(collaboration)]== 1, v1, v0) 
collaboration_score <-
  t(collaboration_score)
collaboration_score[upper.tri(collaboration_score)] <-
  if_else(collaboration[lower.tri(collaboration)]== 1, v1, v0)

# 共著ネットワーク
diag(collaboration) <- 0
collabo_g <- collaboration |>
  graph_from_adjacency_matrix(mode = "undirected")

set.seed(0)

par(mfrow = c(2, 2), mar = c(0,0,0,0))

collabo_g |>
  plot(layout = layout_in_circle)

collabo_g |>
  plot()

# 類似度ネットワーク
diag(collaboration_score) <- 0
score_g <- collaboration_score |>
  graph_from_adjacency_matrix(mode = "undirected", weighted = TRUE)

jet.colors <- colorRampPalette(c("#00007F", "blue", "#007FFF", "cyan", "#7FFF7F", "yellow", "#FF7F00", "red", "#7F0000"))
col_p <- round((E(score_g)$weight / max(E(score_g)$weight)) * 100, 0)

set.seed(0)

collabo_g |>
  plot(
    layout = layout_in_circle,
    edge.width = E(score_g)$weight * 10,
    edge.color = jet.colors(100)[col_p]
    )

score_g |>
  plot(
    edge.width = E(score_g)$weight * 10,
    edge.color = jet.colors(100)[col_p]
    )

par(mfrow = c(1, 1), mar = c(5.1, 4.1, 4.1, 2.1))

4.2.3 指導関係の可視化

4.2.3.1
library(conflicted)
library(tidyverse)

# 研究者リスト
researchers <- c("A", "B", "C", "D", "E", "F", "G", "H", "I", "J")

# 共著データ
collaboration <- matrix(
  c(
    NA, 1, 1, 0, 0, 0, 0, 0, 0, 1,
    0, NA, 0, 1, 1, 1, 0, 0, 0, 0,
    0, 0, NA, 0, 0, 0, 1, 1, 1, 0,
    0, 0, 0, NA, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, NA, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, NA, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, NA, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, NA, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, NA, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, NA
    ),
  nrow = 10,
  dimnames = list(researchers, researchers)
  )

# 共著ネットワーク
collaboration |>
  as.data.frame() |>
  rownames_to_column() |>
  pivot_longer(!rowname) |>
  mutate(
    value = factor(value),
    name = factor(name, levels = rev(LETTERS[1:10]))
    ) |>
  ggplot(aes(x = rowname, y = name, fill = value, label = value)) +
  geom_tile() +
  geom_text() +
  scale_fill_hue(name = "", labels = c("0" = "指導関係なし", "1" ="指導関係あり")) +
  labs(title = "隣接行列表示", x = "指導された研究者", y = "指導した研究者") +
  theme(aspect.ratio = 1)

4.2.3.2
library(conflicted)
library(tidyverse)
library(igraph)

# 研究者リスト
researchers <- c("A", "B", "C", "D", "E", "F", "G", "H", "I", "J")

# 共著データ
collaboration <- matrix(
  c(
    NA, 1, 1, 0, 0, 0, 0, 0, 0, 1,
    0, NA, 0, 1, 1, 1, 0, 0, 0, 0,
    0, 0, NA, 0, 0, 0, 1, 1, 1, 0,
    0, 0, 0, NA, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, NA, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, NA, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, NA, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, NA, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, NA, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, NA
    ),
  nrow = 10,
  dimnames = list(researchers, researchers)
  )

diag(collaboration) <- 0

par(mar = c(0,0,0,0))

collaboration |>
  t() |>
  graph_from_adjacency_matrix(mode = "directed") |>
  plot(layout = layout_as_tree)

par(mar = c(5.1, 4.1, 4.1, 2.1))

4.2.4 様々なレイアウトによるネットワーク描画

circoレイアウトがigraphには無いようなのでMDSレイアウトで代用。

library(conflicted)
library(tidyverse)
library(igraph)

set.seed(0)
G_er <- erdos.renyi.game(30, 0.2)
G_ws <- watts.strogatz.game(1, 30, 5, 0.1)
G_ba <- barabasi.game(30, 1)

ErdosR <- as_adjacency_matrix(G_er, sparse = FALSE)
WattsStrogatz <- as_adjacency_matrix(G_ws, sparse = FALSE)
BarabasiAlbert <- as_adjacency_matrix(G_ba, sparse = FALSE)

net1 <- graph_from_adjacency_matrix(ErdosR, mode = "max")
net2 <- graph_from_adjacency_matrix(WattsStrogatz, mode = "max")
net3 <- graph_from_adjacency_matrix(BarabasiAlbert, mode = "max")

par(mfrow = c(3,3), mar = c(0,0,1,0))
plot(net1, layout = layout_in_circle,
     main = "Erdos-Reyni: Circular Layout", vertex.size = 9, vertex.label=NA, )
plot(net2, layout = layout_in_circle,
     main = "Watts-Strogatz: Circular Layout", vertex.size = 9, vertex.label=NA)
plot(net3, layout = layout_in_circle,
     main = "Barabasi-Albert: Circular Layout", vertex.size = 9, vertex.label=NA)

plot(net1, layout = layout_with_mds,
     main = "Erdos-Reyni: MDS Layout", vertex.size = 9, vertex.label=NA)
plot(net2, layout = layout_with_mds,
     main = "Watts-Strogatz: MDS Layout", vertex.size = 9, vertex.label=NA)
plot(net3, layout = layout_with_mds,
     main = "Barabasi-Albert: MDS Layout", vertex.size = 9, vertex.label=NA)

plot(net1, layout = layout_with_kk(net1),
     main = "Erdos-Reyni: KK Layout", vertex.size = 9, vertex.label=NA)
plot(net2, layout = layout_with_kk(net2),
     main = "Watts-Strogatz: KK Layout", vertex.size = 9, vertex.label=NA)
plot(net3, layout = layout_with_kk(net3),
     main = "Barabasi-Albert: KK Layout", vertex.size = 9, vertex.label=NA)

par(mfrow = c(1,1), mar = c(5.1, 4.1, 4.1, 2.1))

4.2.5 有向ネットワークの可視化

dotとcircoが無いのでtree, mdsで代用

library(conflicted)
library(tidyverse)
library(igraph)

# ランダム有向グラフを生成
set.seed(0)
G_dir_random <- sample_gnm(30, 81, directed = TRUE) 

# 階層構造を持つ有向グラフを生成
set.seed(0)
G_dir_hierarchy <- sample_tree(30, directed = TRUE)

my_plot <- function(data, layout){
  plot(
    data, layout = layout,
    vertex.label = NA,
    edge.arrow.size = 0.5
    )
}
par(mfrow = c(3,2), mar = c(0,0,0,0))
my_plot(G_dir_random, layout_as_tree)
my_plot(G_dir_hierarchy, layout_as_tree)
my_plot(G_dir_random, layout_with_mds)
my_plot(G_dir_hierarchy, layout_with_mds)
my_plot(G_dir_random, layout_with_kk)
my_plot(G_dir_hierarchy, layout_with_kk)

par(mfrow = c(1,1), mar = c(5.1, 4.1, 4.1, 2.1))

4.3.1 クラスターマップによるデータの可視化

library(conflicted)
library(tidyverse)
library(pheatmap)

df <- read_csv(
  "https://archive.ics.uci.edu/ml/machine-learning-databases/wine/wine.data",
  col_names = c(
    "ブドウの品種", "アルコール度数", "リンゴ酸", "ミネラル分", 
    "ミネラル分のアルカリ度", "マグネシウム", "全フェノール類", "フラバノイド",
    "非フラバノイドフェノール類", "プロアントシアニン", "色の強さ", "色相",
    "OD280/OD315値", "プロリン"
  ),
  col_types = "f"
) |>
  mutate(across(where(is.numeric), \(x) scale(x))) #標準化

jet.colors <- colorRampPalette(c("#00007F", "blue", "#007FFF", "cyan", "#7FFF7F", "yellow", "#FF7F00", "red", "#7F0000"))

pheatmap(
  df |>
    dplyr::select(!ブドウの品種) |>
    t(),
  color = jet.colors(50),
  clustering_method = "ward.D2"
  )

4.3.3 様々なクラスタリング手法

BIRCHだけ見つからないので省略。

ちなみにRではmlbenchパッケージにベンチマーク用の様々なデータセットと人工データ生成用の関数が用意されています。

library(conflicted)
library(tidyverse)
library(ClusterR)   # MiniBatch KMeans
library(apcluster)  # Affinity Propagation
library(meanShiftR) # MeanShift
library(skmeans)    # Spectral Clustering
library(cluster)    # Agglomerative Clustering
library(dbscan)     # DBSCAN, HDBSCAN, OPTICS,
library(mclust)     # Gaussian Mixture
library(patchwork)

# データ用意
my_read_csv <- function(file){
  read_csv(file, col_names = c("x", "y", "class")) |>
    mutate( #標準化しておく
      x = (x - mean(x))/sd(x),
      y = (y - mean(x))/sd(x),  
      class = factor(class + 1))
}

# 円形のクラスタ
noisy_circles <- my_read_csv(
  "https://raw.githubusercontent.com/morimotoosamu/data_visualization/main/data/noisy_circles.csv"
  )

# 月型のクラスタ
noisy_moons <- my_read_csv(
  "https://raw.githubusercontent.com/morimotoosamu/data_visualization/main/data/noisy_moons.csv"
  )     

# 正規分布に従うクラスタ
blobs <- my_read_csv(
  "https://raw.githubusercontent.com/morimotoosamu/data_visualization/main/data/blobs.csv"
  )    

# 異方性のあるデータ
aniso <- my_read_csv(
  "https://raw.githubusercontent.com/morimotoosamu/data_visualization/main/data/aniso.csv"
  )       

# 3つの正規分布に従うデータ
varied <- my_read_csv(
  "https://raw.githubusercontent.com/morimotoosamu/data_visualization/main/data/varied.csv"
  )               

n <- 500
set.seed(0)
no_structure <- data.frame(x = runif(n), y = runif(n), class = factor("0"))# 構造のないデータ

# 各手法のラッパー関数を用意
# MiniBatch KMeans
my_MiniBatchKmeans <- function(data, cluster_num) {
  data_cleaned <- data[, 1:2]
  start <- Sys.time()
  fit <- MiniBatchKmeans(data_cleaned, clusters = cluster_num)
  pred <- predict(fit, data_cleaned)
  end <- Sys.time()
  diff <- end - start
  data$pred <- as.factor(pred)
  return(list(res = data, diff = diff))
}

# Affinity Propagation
my_apcluster <- function(data, cluster_num) {
  data_cleaned <- data[, 1:2]
  start <- Sys.time()
  pred <- apcluster(s = negDistMat(r=2), x = data_cleaned, p = -200, q = 0.9) |>
    cutree(cluster_num) |>
    labels(type = "enum")
  end <- Sys.time()
  diff <- end - start
  data$pred <- as.factor(pred)
  return(list(res = data, diff = diff))
}

# MeanShift
my_meanShift <- function(data) {
  data_cleaned <- as.matrix(data[, 1:2])
  start <- Sys.time()
  pred <- meanShift(data_cleaned, data_cleaned)$assignment
  end <- Sys.time()
  diff <- end - start
  data$pred <- as.factor(pred)
  return(list(res = data, diff = diff))
}

# Spectral Clustering
my_skmeans <- function(data, cluster_num) {
  data_cleaned <- base::as.matrix(data[, 1:2])
  start <- Sys.time()
  pred <- skmeans(data_cleaned, k = cluster_num)$cluster
  end <- Sys.time()
  diff <- end - start
  data$pred <- as.factor(pred)
  return(list(res = data, diff = diff))
}

# Ward
my_hclust <- function(data, cluster_num) {
  data_cleaned <- data[, 1:2]
  start <- Sys.time()
  pred <- data_cleaned |>
    stats::dist() |>
    hclust(method = "ward.D2") |>
    cutree(k = cluster_num)
  end <- Sys.time()
  diff <- end - start
  data$pred <- as.factor(pred)
  return(list(res = data, diff = diff))
}

# Agglomerative Clustering
my_agnes <- function(data, cluster_num) {
  data_cleaned <- data[, 1:2]
  start <- Sys.time()
  pred <- agnes(data_cleaned) |> cutree(k = cluster_num)
  end <- Sys.time()
  diff <- end - start
  data$pred <- as.factor(pred)
  return(list(res = data, diff = diff))
}

# DBSCAN
my_dbscan <- function(data) {
  data_cleaned <- data[, 1:2]
  start <- Sys.time()
  pred <- dbscan::dbscan(data_cleaned, eps = 0.3)$cluster
  end <- Sys.time()
  diff <- end - start
  data$pred <- as.factor(pred)
  return(list(res = data, diff = diff))
}

# HDBSCAN
my_hdbscan <- function(data) {
  data_cleaned <- data[, 1:2]
  start <- Sys.time()
  pred <- dbscan::hdbscan(data_cleaned, minPts = 15)$cluster
  end <- Sys.time()
  diff <- end - start
  data$pred <- as.factor(pred)
  return(list(res = data, diff = diff))
}

# OPTICS
my_optics <- function(data) {
  data_cleaned <- data[, 1:2]
  start <- Sys.time()
  pred <- dbscan::optics(data_cleaned, eps = 0.1, minPts = 7) |>
    extractXi(xi = 0.05) |>
    pluck("cluster")
  end <- Sys.time()
  diff <- end - start
  data$pred <- as.factor(pred)
  return(list(res = data, diff = diff))
}

# Gaussian Mixture
my_Mclust <- function(data) {
  data_cleaned <- data[, 1:2]
  start <- Sys.time()
  pred <- mclust::Mclust(data_cleaned, G = 1:3)$classification
  end <- Sys.time()
  diff <- end - start
  data$pred <- as.factor(pred)
  return(list(res = data, diff = diff))
}

### クラスタリング実行
dats <- list(noisy_circles, noisy_moons, varied, aniso, blobs, no_structure)
cnums <- list(2,2,3,3,3,3)

set.seed(0)
res_clustering <- list(
  res_MiniBatchKmeans = map2(dats, cnums, \(dats, cnums) my_MiniBatchKmeans(dats, cnums)),
  res_apcluster       = map2(dats, cnums, \(dats, cnums) my_apcluster(dats, cnums)),
  res_meanShift       = purrr::map(dats, \(dats) my_meanShift(dats)),
  res_skmeans         = map2(dats, cnums, \(dats, cnums) my_skmeans(dats, cnums)),
  res_hclust          = map2(dats, cnums, \(dats, cnums) my_hclust(dats, cnums)),
  res_agnes           = map2(dats, cnums, \(dats, cnums) my_agnes(dats, cnums)),
  res_dbscan          = purrr::map(dats, \(dats) my_dbscan(dats)),
  res_hdbscan         = purrr::map(dats, \(dats) my_hdbscan(dats)),
  res_optics          = purrr::map(dats, \(dats) my_optics(dats)),
  res_Mclust          = purrr::map(dats, \(dats) my_Mclust(dats))
) 

# 描画用ラッパー関数を用意
my_plot <- function(result) {
  result$res |>
    ggplot(aes(x = x, y = y, color = pred)) +
    geom_point(size = 1) + 
    labs(caption = paste0(round(result$diff,3),"s")) +
    theme(
      axis.ticks = element_blank(),  # tickの線を消す
      axis.text = element_blank(),   # tickの数字を消す
      axis.title = element_blank(),  # 軸のラベルを消す
      axis.line = element_blank(),   # 軸の線を消す
      legend.position="none",
      aspect.ratio = 1
      )
}

nums <- expand_grid(d = 1:6, m = 1:10)
res_plot <- map2(nums$m, nums$d, \(.x, .y) my_plot(res_clustering[[.x]][[.y]]))

# ここがダサい……もうちょっとどうにかならないか
res_plot[[1]] + res_plot[[2]] +res_plot[[3]] +res_plot[[4]] +res_plot[[5]] +res_plot[[6]] +
  res_plot[[7]] + res_plot[[8]] +res_plot[[9]] +res_plot[[10]] +res_plot[[11]] +res_plot[[12]] +
  res_plot[[13]] + res_plot[[14]] +res_plot[[15]] +res_plot[[16]] +res_plot[[17]] +res_plot[[18]] +
  res_plot[[19]] + res_plot[[20]] +res_plot[[21]] +res_plot[[22]] +res_plot[[23]] +res_plot[[24]] +
  res_plot[[25]] + res_plot[[26]] +res_plot[[27]] +res_plot[[28]] +res_plot[[29]] +res_plot[[30]] +
  res_plot[[31]] + res_plot[[32]] +res_plot[[33]] +res_plot[[34]] +res_plot[[35]] +res_plot[[36]] +
  res_plot[[37]] + res_plot[[38]] +res_plot[[39]] +res_plot[[40]] +res_plot[[41]] +res_plot[[42]] +
  res_plot[[43]] + res_plot[[44]] +res_plot[[45]] +res_plot[[46]] +res_plot[[47]] +res_plot[[48]] +
  res_plot[[49]] + res_plot[[50]] +res_plot[[51]] +res_plot[[52]] +res_plot[[53]] +res_plot[[54]] +
  res_plot[[55]] + res_plot[[56]] +res_plot[[57]] +res_plot[[58]] +res_plot[[59]] +res_plot[[60]] +
  plot_layout(ncol = 10)

4.3.4 多変数をペアプロットで見る

library(conflicted)
library(tidyverse)
library(GGally)

df <- read_csv(
  "https://raw.githubusercontent.com/morimotoosamu/data_visualization/main/data/df_434.csv"
  )

df |>
  ggpairs()

4.3.5 主成分分析のイメージ

library(conflicted)
library(tidyverse)
library(skmeans)
library(GGally)
library(patchwork)

df <- read_csv(
  "https://raw.githubusercontent.com/morimotoosamu/data_visualization/main/data/df_434.csv"
  )

# 主成分分析(標準化)
pca_result <- prcomp(df)#, scale. = TRUE)
pca_importance <- as.data.frame(summary(pca_result)$importance[2,]) |>
  rownames_to_column()
names(pca_importance) <- c("pc", "value")

# Spectral Clustering
clusters_pca <- skmeans(pca_result$x[, 1:2], 3)

p1 <- data.frame(
  pc1 = pca_result$x[, 1],
  pc2 = pca_result$x[, 2],
  class = factor(clusters_pca$cluster)
    ) |>
  ggplot(aes(x = pc1, y = pc2, color = class)) +
  geom_point() +
  labs(title = "二つの主成分で見る")+
  theme(legend.position="none", aspect.ratio = 1)

p2 <- pca_importance |>
  ggplot(aes(x = reorder(pc, desc(value)), y = value)) +
  geom_col()+
  labs(title = "各主成分のデータ悦明力", x = "", y = "")+
  theme(aspect.ratio = 1)

p1 + p2

4.3.6 画像データの次元削減

library(conflicted)
library(tidyverse)
library(MASS) # MDS(sammon)
library(Rtsne) # t-SNE
library(umap) # UMAP

df <- read_csv(
  "https://raw.githubusercontent.com/morimotoosamu/data_visualization/main/data/digits.csv"
  )

df_cleaned <- df |>
  dplyr::select(!target)

# 各手法で2次元に圧縮
# 主成分分析
X_pca <- prcomp(df_cleaned)$x[, 1:2]

# t-SNE
set.seed(42)
X_tsne <- Rtsne(df_cleaned, num_threads = 2)$Y

# MDS
X_mds <- df_cleaned |>
  dist() |>
  sammon(trace = FALSE) |>
  pluck("points")

# UMAP
set.seed(42)
X_umap <- umap(df_cleaned)$layout

# K-means
set.seed(42)
clusters_pca <- kmeans(X_pca, 10)$cluster  # PCA
set.seed(42)
clusters_mds <- kmeans(X_mds, 10)$cluster #MDS
set.seed(42)
clusters_tsne <- kmeans(X_tsne, 10)$cluster # t-SNE
set.seed(42)
clusters_umap <- kmeans(X_umap, 10)$cluster  # UMAP

# 結果をデータフレームにまとめる
df_base <- data.frame(
    x = c(X_pca[, 1], X_mds[, 1], X_tsne[, 1], X_umap[, 1]),
    y = c(X_pca[, 2], X_mds[, 2], X_tsne[, 2], X_umap[, 2])
    )

n <- 1797

dimred <- bind_rows(
  df_base |>
    mutate(
      label = rep(df$target, 4),
      method = c(rep("pca_label", n), rep("mds_label", n),rep("tsne_label", n),rep("umap_label", n))
      ),
  df_base |>
    mutate(
      label = c(clusters_pca, clusters_mds, clusters_tsne, clusters_umap),
      method = c(rep("pca_kmeans", n), rep("mds_kmeans", n),rep("tsne_kmeans", n),rep("umap_kmeans", n))
      )
) |>
  mutate(
    method = factor(
      method,
      levels = c("pca_kmeans", "pca_label", "mds_kmeans", "mds_label",
                 "tsne_kmeans",  "tsne_label", "umap_kmeans", "umap_label")),
    label = factor(label)
    )

# クラスタリング結果と正解ラベルの描画
dimred |>
  ggplot(aes(x = x, y = y, color = label)) + 
  geom_point() + 
  labs(title="様々な次元圧縮方法") +
  theme(
    axis.ticks = element_blank(),  # tickの線を消す
    axis.text = element_blank(),   # tickの数字を消す
    axis.title = element_blank(),  # 軸のラベルを消す
    axis.line = element_blank(),   # 軸の線を消す
    legend.position="none",
    aspect.ratio = 1
  ) +
  facet_wrap(vars(method), nrow = 2, scales = "free")

第4章はここまで。

LS0tCnRpdGxlOiAi56ysNOeroCDlpJrlpInmlbDjgpLjgajjgonjgYjjgovjg4fjg7zjgr/lj6/oppbljJYiCmF1dGhvcjogIk9zYW11LCBNT1JJTU9UTyIKZGF0ZTogImByIFN5cy5EYXRlKClgIgpvdXRwdXQ6CiAgaHRtbF9kb2N1bWVudDogCiAgICBjb2RlX2Rvd25sb2FkOiB0cnVlCiAgICB0b2M6IHllcwogICAgdG9jX2RlcHRoOiAzCiAgICB0aGVtZTogdW5pdGVkICAgIAogICAgbWRfZXh0ZW5zaW9uczogIi1hc2NpaV9pZGVudGlmaWVycyIKICAgIHRvY19mbG9hdDogeWVzCiAgICBmaWdfd2lkdGg6IDcuNQogICAgZmlnX2hlaWdodDogNS42MjUKICAgIGRldjogcmFnZ19wbmcKICAgIGhpZ2hsaWdodDogdGFuZ28KICAgIGNvZGVfZm9sZGluZzogaGlkZQogICAgZGZfcHJpbnQ6IHBhZ2VkCi0tLQoKYGBge3Igc2V0dXAsIGluY2x1ZGU9RkFMU0V9CmtuaXRyOjpvcHRzX2NodW5rJHNldChlY2hvID0gVFJVRSkKYGBgCgrlm7Pjga7lj7PkuIrjga5gc2hvd2Djg5zjgr/jg7PjgpLmirzjgZnjgahS44Gu44Kz44O844OJ44GM6KGo56S644GV44KM44G+44GZ44CCCgojIyA0LjEg5LiJ44Gk5Lul5LiK44Gu5aSJ5pWw44Gu5Y+v6KaW5YyWCgojIyMgNC4xLjEg44Os44O844OA44O844OB44Oj44O844OI44Gu5Y2w6LGhCgp+flLjgafjg6zjg7zjg4Djg7zjg4Hjg6Pjg7zjg4jjgpLmj4/jgY/jg5Hjg4PjgrHjg7zjgrjjga/jgYTjgY/jgaTjgYvjgYLjgovjga7jgaDjgYzjgIHjganjgozjgoLjgqTjg57jgqTjg4HntI3lvpfjgYTjgYvjgarjgYvjgaPjgZ/jga7jgafjg53jg7zjg6njg7zjg4Hjg6Pjg7zjg4jjgafli5jlvIHjgZfjgabkuIvjgZXjgYTjgIJ+fgoKW+S4rea+pOWFiOeUn10oaHR0cHM6Ly90d2l0dGVyLmNvbS9NaW5hdG9OYWthemF3YSnjgYvjgonmlZnjgYjjgabjgYTjgZ/jgaDjgYTjgZ9bZm1zYuODkeODg+OCseODvOOCuOOCkuS9v+OBhuaWueazlV0oaHR0cHM6Ly9taW5hdG8uc2lwMjFjLm9yZy9pbTNyLzIwMjQwMTExLmh0bWwp44Gn44Kt44Os44Kk44Gr5o+P44GR44G+44GX44Gf77yBCgpmbXNi44OR44OD44Kx44O844K444Gu5pel5pys6Kqe44Oe44OL44Ol44Ki44Or44GvW+OBk+OBoeOCiV0oaHR0cHM6Ly9taW5hdG8uc2lwMjFjLm9yZy9tc2IvbWFuL2luZGV4Lmh0bWwp44CCCgpgYGB7cn0KbGlicmFyeShjb25mbGljdGVkKQpsaWJyYXJ5KHRpZHl2ZXJzZSkKbGlicmFyeShmbXNiKQoKZGF0YTEgPC0gZGF0YS5mcmFtZSgKICDlm73oqp4gPSBjKDUsIDEsIDUsIDMpLAogIOeQhuenkSA9IGMoNSwgMSwgNSwgNCksCiAg56S+5LyaID0gYyg1LCAxLCA0LCAzKSwKICDkvZPogrIgPSBjKDUsIDEsIDQsIDQpLAogIOmfs+alvSA9IGMoNSwgMSwgNSwgMiksCiAg5pWw5a2mID0gYyg1LCAxLCA1LCAyKQogICkKCmRhdGEyIDwtIGRhdGEuZnJhbWUoCiAg5pWw5a2mID0gYyg1LCAxLCA1LCA1KSwKICDlm73oqp4gPSBjKDUsIDEsIDUsIDEpLAogIOeQhuenkSA9IGMoNSwgMSwgMSwgNSksCiAg56S+5LyaID0gYyg1LCAxLCAxLCAxKSwKICDkvZPogrIgPSBjKDUsIDEsIDEsIDUpLAogIOmfs+alvSA9IGMoNSwgMSwgNSwgMSkKICApCgpwYXIobWZyb3cgPSBjKDIsIDIpLCBvbWEgPSBjKDAsMCwwLDApLCBtYXIgPSBjKDAsMCwwLDApKQojIHBsb3QxCmRhdGExIHw+CiAgc2VsZWN0KOaVsOWtpiwg5Zu96KqeLCDnkIbnp5EsIOekvuS8miwg5L2T6IKyLCDpn7Pmpb0pIHw+CiAgcmFkYXJjaGFydCgKICAgIGF4aXN0eXBlID0gNCwgc2VnID0gNCwgcHR5ID0gMzIsIHBjb2wgPSBjKDQsIDIpLAogICAgcGZjb2wgPSBjKGFkanVzdGNvbG9yKCJsaWdodGJsdWUiLCAwLjUpLCBhZGp1c3Rjb2xvcigicGluayIsIDAuNSkpLAogICAgY2F4aXNsYWJlbHM9c3ByaW50ZigiJWQiLCAxOjUpCiAgICApIAp0ZXh0KC0wLjQsIC0wLjMsICAiQeOBleOCkyIsIGNvbD0icmVkIikKdGV4dCgtMC40LCAwLjYsIkLjgZXjgpMiLCBjb2w9ImJsdWUiKQoKIyBwbG90MgpkYXRhMSB8PgogIHNlbGVjdCjpn7Pmpb0sIOaVsOWtpiwg55CG56eRLCDkvZPogrIsIOekvuS8miwg5Zu96KqeKSB8PgogIHJhZGFyY2hhcnQoCiAgICBheGlzdHlwZSA9IDQsIHNlZyA9IDQsIHB0eSA9IDMyLCBwY29sID0gYyg0LCAyKSwKICAgIHBmY29sID0gYyhhZGp1c3Rjb2xvcigibGlnaHRibHVlIiwgMC41KSwgYWRqdXN0Y29sb3IoInBpbmsiLCAwLjUpKSwKICAgIGNheGlzbGFiZWxzPXNwcmludGYoIiVkIiwgMTo1KQogICAgKSAKdGV4dCgtMC40LCAtMC4zLCAiQeOBleOCkyIsIGNvbD0icmVkIikKdGV4dCgtMC40LCAwLjYsICJC44GV44KTIiwgY29sPSJibHVlIikKCiMgcGxvdDMKZGF0YTIgfD4KICBzZWxlY3Qo5pWw5a2mLCDlm73oqp4sIOeQhuenkSwg56S+5LyaLCDkvZPogrIsIOmfs+alvSkgfD4KICByYWRhcmNoYXJ0KAogICAgYXhpc3R5cGUgPSA0LCBzZWcgPSA0LCBwdHkgPSAzMiwgcGNvbCA9IGMoNCwgMiksCiAgICBwZmNvbCA9IGMoYWRqdXN0Y29sb3IoImxpZ2h0Ymx1ZSIsIDAuNSksIGFkanVzdGNvbG9yKCJwaW5rIiwgMC41KSksCiAgICBjYXhpc2xhYmVscz1zcHJpbnRmKCIlZCIsIDE6NSkKICAgICkgCnRleHQoLTAuNCwgLTAuMywgIkHjgZXjgpMiLCBjb2w9InJlZCIpCnRleHQoLTAuNCwgMC42LCAiQuOBleOCkyIsIGNvbD0iYmx1ZSIpCgojIHBsb3Q0CmRhdGEyIHw+CiAgc2VsZWN0KOmfs+alvSwg5pWw5a2mLCDnkIbnp5EsIOS9k+iCsiwg56S+5LyaLCDlm73oqp4pIHw+CiAgcmFkYXJjaGFydCgKICAgIGF4aXN0eXBlID0gNCwgc2VnID0gNCwgcHR5ID0gMzIsIHBjb2wgPSBjKDQsIDIpLAogICAgcGZjb2wgPSBjKGFkanVzdGNvbG9yKCJsaWdodGJsdWUiLCAwLjUpLCBhZGp1c3Rjb2xvcigicGluayIsIDAuNSkpLAogICAgY2F4aXNsYWJlbHM9c3ByaW50ZigiJWQiLCAxOjUpCiAgICApIAp0ZXh0KC0wLjQsIC0wLjMsICJB44GV44KTIiwgY29sPSJyZWQiKQp0ZXh0KC0wLjQsIDAuNiwgIkLjgZXjgpMiLCBjb2w9ImJsdWUiKQpwYXIobWZyb3cgPSBjKDEsIDEpKQpgYGAKCmBgYHtyIG1lc3NhZ2U9RkFMU0UsIHdhcm5pbmc9RkFMU0V9CmxpYnJhcnkoY29uZmxpY3RlZCkKbGlicmFyeSh0aWR5dmVyc2UpCmxpYnJhcnkocGF0Y2h3b3JrKQoKZGF0YTEgPC0gZGF0YS5mcmFtZSgKICBwZXJzb24gPSBjKCJB44GV44KTIiwgIkLjgZXjgpMiKSwgCiAg5pWw5a2mID0gYyg1LCAyKSwKICDlm73oqp4gPSBjKDUsIDMpLAogIOeQhuenkSA9IGMoNSwgNCksCiAg56S+5LyaID0gYyg0LCAzKSwKICDkvZPogrIgPSBjKDQsIDQpLAogIOmfs+alvSA9IGMoNSwgMikKICApIHw+CiAgcGl2b3RfbG9uZ2VyKCFwZXJzb24pCgojIGNvbXBlbGxpbmcgZGF0YQpkYXRhMiA8LSBkYXRhLmZyYW1lKAogIHBlcnNvbiA9IGMoJ0HjgZXjgpMnLCAnQuOBleOCkycpLAogIOaVsOWtpiA9IGMoNSwgNSksCiAg5Zu96KqeID0gYyg1LCAxKSwKICDnkIbnp5EgPSBjKDEsIDUpLAogIOekvuS8miA9IGMoMSwgMSksCiAg5L2T6IKyID0gYygxLCA1KSwKICDpn7Pmpb0gPSBjKDUsIDEpCikgfD4KICBwaXZvdF9sb25nZXIoIXBlcnNvbikKCiMg5Lim44GzMQpwMSA8LSBkYXRhMSB8PgogIG11dGF0ZShuYW1lID0gZmFjdG9yKG5hbWUsIGxldmVscyA9IGMoIuaVsOWtpiIsICLlm73oqp4iLCAi55CG56eRIiwgIuekvuS8miIsICLkvZPogrIiLCAi6Z+z5qW9IikpKSB8PgogIGdncGxvdChhZXMoeCA9IG5hbWUsIHkgPSB2YWx1ZSwgZmlsbCA9IHBlcnNvbiwgZ3JvdXAgPSBwZXJzb24pKSArCiAgZ2VvbV9jb2wocG9zaXRpb24gPSBwb3NpdGlvbl9kb2RnZSh3aWR0aD0xKSkgKwogIGNvb3JkX3BvbGFyKCkgKwogICAgdGhlbWUoCiAgICAgIGxlZ2VuZC5wb3NpdGlvbj0ibm9uZSIsIAogICAgICBheGlzLnRpdGxlLng9ZWxlbWVudF9ibGFuaygpLCAKICAgICAgYXhpcy50aXRsZS55PWVsZW1lbnRfYmxhbmsoKQogICAgKQoKIyDkuKbjgbMyCnAyIDwtIGRhdGExIHw+CiAgbXV0YXRlKG5hbWUgPSBmYWN0b3IobmFtZSwgbGV2ZWxzID0gYygi6Z+z5qW9IiwgIuaVsOWtpiIsICLnkIbnp5EiLCAi5L2T6IKyIiwgIuekvuS8miIsICLlm73oqp4iKSkpIHw+CiAgZ2dwbG90KGFlcyh4ID0gbmFtZSwgeSA9IHZhbHVlLCBmaWxsID0gcGVyc29uLCBncm91cCA9IHBlcnNvbikpICsKICBnZW9tX2NvbChwb3NpdGlvbiA9IHBvc2l0aW9uX2RvZGdlKHdpZHRoPTEpKSArCiAgY29vcmRfcG9sYXIoKSArCiAgICB0aGVtZSgKICAgICAgbGVnZW5kLnBvc2l0aW9uPSJub25lIiwgCiAgICAgIGF4aXMudGl0bGUueD1lbGVtZW50X2JsYW5rKCksIAogICAgICBheGlzLnRpdGxlLnk9ZWxlbWVudF9ibGFuaygpCiAgICApCgojIOS4puOBszEKcDMgPC0gZGF0YTIgfD4KICBtdXRhdGUobmFtZSA9IGZhY3RvcihuYW1lLCBsZXZlbHMgPSBjKCLmlbDlraYiLCAi5Zu96KqeIiwgIueQhuenkSIsICLnpL7kvJoiLCAi5L2T6IKyIiwgIumfs+alvSIpKSkgfD4KICBnZ3Bsb3QoYWVzKHggPSBuYW1lLCB5ID0gdmFsdWUsIGZpbGwgPSBwZXJzb24sIGdyb3VwID0gcGVyc29uKSkgKwogIGdlb21fY29sKHBvc2l0aW9uID0gcG9zaXRpb25fZG9kZ2Uod2lkdGg9MSkpICsKICBjb29yZF9wb2xhcigpICsKICAgIHRoZW1lKAogICAgICBsZWdlbmQucG9zaXRpb249Im5vbmUiLCAKICAgICAgYXhpcy50aXRsZS54PWVsZW1lbnRfYmxhbmsoKSwgCiAgICAgIGF4aXMudGl0bGUueT1lbGVtZW50X2JsYW5rKCkKICAgICkKCiMg5Lim44GzMgpwNCA8LSBkYXRhMiB8PgogIG11dGF0ZShuYW1lID0gZmFjdG9yKG5hbWUsIGxldmVscyA9IGMoIumfs+alvSIsICLmlbDlraYiLCAi55CG56eRIiwgIuS9k+iCsiIsICLnpL7kvJoiLCAi5Zu96KqeIikpKSB8PgogIGdncGxvdChhZXMoeCA9IG5hbWUsIHkgPSB2YWx1ZSwgZmlsbCA9IHBlcnNvbiwgZ3JvdXAgPSBwZXJzb24pKSArCiAgZ2VvbV9jb2wocG9zaXRpb24gPSBwb3NpdGlvbl9kb2RnZSh3aWR0aD0xKSkgKwogIGNvb3JkX3BvbGFyKCkgKwogICAgdGhlbWUoCiAgICAgIGxlZ2VuZC5wb3NpdGlvbj0ibm9uZSIsIAogICAgICBheGlzLnRpdGxlLng9ZWxlbWVudF9ibGFuaygpLCAKICAgICAgYXhpcy50aXRsZS55PWVsZW1lbnRfYmxhbmsoKQogICAgKQoKKHAxICsgcDIpIC8gKHAzICsgcDQpCmBgYAoKIyMjIDQuMS4yIOWQhOWkieaVsOOBrueJueW+tOOCkuamguims+OBl+OBpuavlOi8g+OBmeOCiwoKYGBge3IgbWVzc2FnZT1GQUxTRSwgd2FybmluZz1GQUxTRX0KbGlicmFyeShjb25mbGljdGVkKQpsaWJyYXJ5KHRpZHl2ZXJzZSkKbGlicmFyeShwYXRjaHdvcmspCgp2X25hbWVzIDwtIGMoCiAgICAi44OW44OJ44Km44Gu5ZOB56iuIiwgIuOCouODq+OCs+ODvOODq+W6puaVsCIsICLjg6rjg7PjgrTphbgiLCAi44Of44ON44Op44Or5YiGIiwgCiAgICAi44Of44ON44Op44Or5YiG44Gu44Ki44Or44Kr44Oq5bqmIiwgIuODnuOCsOODjeOCt+OCpuODoCIsICLlhajjg5Xjgqfjg47jg7zjg6vpoZ4iLCAi44OV44Op44OQ44OO44Kk44OJIiwKICAgICLpnZ7jg5Xjg6njg5Djg47jgqTjg4njg5Xjgqfjg47jg7zjg6vpoZ4iLCAi44OX44Ot44Ki44Oz44OI44K344Ki44OL44OzIiwgIuiJsuOBruW8t+OBlSIsICLoibLnm7giLAogICAgIk9EMjgwL09EMzE15YCkIiwgIuODl+ODreODquODsyIKICApCgpkZiA8LSByZWFkX2NzdigKICAiaHR0cHM6Ly9hcmNoaXZlLmljcy51Y2kuZWR1L21sL21hY2hpbmUtbGVhcm5pbmctZGF0YWJhc2VzL3dpbmUvd2luZS5kYXRhIiwKICBjb2xfbmFtZXMgPSB2X25hbWVzLAogIGNvbF90eXBlcyA9ICJmIgogICkgfD4KICBtdXRhdGUoYWNyb3NzKHdoZXJlKGlzLm51bWVyaWMpLCBcKHgpIHNjYWxlKHgpKSkgfD4gI+aomea6luWMlgogIHJvd2lkX3RvX2NvbHVtbigpIHw+CiAgcGl2b3RfbG9uZ2VyKCFjKOODluODieOCpuOBruWTgeeoriwgcm93aWQpKSB8PgogIG11dGF0ZShuYW1lID0gZmFjdG9yKG5hbWUsIGxldmVscyA9IHZfbmFtZXMpKQoKZGYgfD4KICBnZ3Bsb3QoYWVzKHggPSBuYW1lLCB5ID0gdmFsdWUsIGNvbG91ciA9IOODluODieOCpuOBruWTgeeoriwgZ3JvdXAgPXJvd2lkKSkgKwogIGdlb21fbGluZShhbHBoYSA9IDAuNSkgKwogIGNvb3JkX2ZsaXAoKSArCiAgbGFicyh0aXRsZSA9ICLjg6/jgqTjg7Pjga7nibnlvrTjgajjg5bjg4njgqbjga7lk4HnqK4iLCB5ID0gIuebuOWvvuOCueOCs+OCoiIsIHggPSAiIikKYGBgCgojIyMgNC4xLjMg5aSJ5pWw44GU44Go44Gr5YCL5Yil44Gr5Y+v6KaW5YyW44GZ44KL5pa55rOVCgpgYGB7ciAgbWVzc2FnZT1GQUxTRSwgd2FybmluZz1GQUxTRX0KbGlicmFyeShjb25mbGljdGVkKQpsaWJyYXJ5KHRpZHl2ZXJzZSkKCnZfbmFtZXMgPC0gYygKICAgICLjg5bjg4njgqbjga7lk4HnqK4iLCAi44Ki44Or44Kz44O844Or5bqm5pWwIiwgIuODquODs+OCtOmFuCIsICLjg5/jg43jg6njg6vliIYiLCAKICAgICLjg5/jg43jg6njg6vliIbjga7jgqLjg6vjgqvjg6rluqYiLCAi44Oe44Kw44ON44K344Km44OgIiwgIuWFqOODleOCp+ODjuODvOODq+mhniIsICLjg5Xjg6njg5Djg47jgqTjg4kiLAogICAgIumdnuODleODqeODkOODjuOCpOODieODleOCp+ODjuODvOODq+mhniIsICLjg5fjg63jgqLjg7Pjg4jjgrfjgqLjg4vjg7MiLCAi6Imy44Gu5by344GVIiwgIuiJsuebuCIsCiAgICAiT0QyODAvT0QzMTXlgKQiLCAi44OX44Ot44Oq44OzIgogICkKCmRmIDwtIHJlYWRfY3N2KAogICJodHRwczovL2FyY2hpdmUuaWNzLnVjaS5lZHUvbWwvbWFjaGluZS1sZWFybmluZy1kYXRhYmFzZXMvd2luZS93aW5lLmRhdGEiLAogIGNvbF9uYW1lcyA9IHZfbmFtZXMsCiAgY29sX3R5cGVzID0gImYiCikgfD4KICBtdXRhdGUoYWNyb3NzKHdoZXJlKGlzLm51bWVyaWMpLCBcKHgpIHNjYWxlKHgpKSkgfD4gI+aomea6luWMlgogIHJvd2lkX3RvX2NvbHVtbigpIHw+CiAgcGl2b3RfbG9uZ2VyKCFjKOODluODieOCpuOBruWTgeeoriwgcm93aWQpKSB8PgogIG11dGF0ZShuYW1lID0gZmFjdG9yKG5hbWUsIGxldmVscyA9IHZfbmFtZXMpKQoKcDEgPC0gZGYgfD4KICBnZ3Bsb3QoYWVzKHggPSBuYW1lLCB5ID0gdmFsdWUsIGdyb3VwID0g44OW44OJ44Km44Gu5ZOB56iuLCBmaWxsID0g44OW44OJ44Km44Gu5ZOB56iuKSkgKwogIHN0YXRfc3VtbWFyeShnZW9tID0gImJhciIsIGZ1biA9ICJtZWFuIiwgcG9zaXRpb24gPSAiZG9kZ2UyIikgKwogIHN0YXRfc3VtbWFyeShnZW9tID0gImVycm9yYmFyIiwgZnVuLmRhdGEgPSAibWVhbl9zZSIsIHBvc2l0aW9uID0gImRvZGdlMiIpICsKICBsYWJzKHkgPSAi55u45a++44K544Kz44KiIiwgeCA9ICIiKSArCiAgdGhlbWUoYXhpcy50ZXh0LnggPSBlbGVtZW50X3RleHQoYW5nbGUgPSA0NSwgaGp1c3QgPSAxKSwKICAgICAgICBhc3BlY3QucmF0aW8gPSAzLzQsCiAgICAgICAgbGVnZW5kLnBvc2l0aW9uID0gIm5vbmUiKQoKcDIgPC0gZGYgfD4KICBnZ3Bsb3QoYWVzKHggPSBuYW1lLCB5ID0gdmFsdWUsIGZpbGwgPSDjg5bjg4njgqbjga7lk4HnqK4pKSArCiAgZ2VvbV92aW9saW4ocG9zaXRpb249ImRvZGdlIikgKwogIGxhYnMoeSA9ICLnm7jlr77jgrnjgrPjgqIiLCB4ID0gIiIpICsKICB0aGVtZShheGlzLnRleHQueCA9IGVsZW1lbnRfdGV4dChhbmdsZSA9IDQ1LCBoanVzdCA9IDEpLAogICAgICAgIGFzcGVjdC5yYXRpbyA9IDMvNCwKICAgICAgICBsZWdlbmQucG9zaXRpb24gPSAibm9uZSIpCgpwMSAvIHAyCmBgYAoKIyMjIDQuMS40IOODkuODvOODiOODnuODg+ODlwoKYGBge3IgIG1lc3NhZ2U9RkFMU0UsIHdhcm5pbmc9RkFMU0V9CmxpYnJhcnkoY29uZmxpY3RlZCkKbGlicmFyeSh0aWR5dmVyc2UpCgp2X25hbWVzIDwtIGMoCiAgICAi44OW44OJ44Km44Gu5ZOB56iuIiwgIuOCouODq+OCs+ODvOODq+W6puaVsCIsICLjg6rjg7PjgrTphbgiLCAi44Of44ON44Op44Or5YiGIiwgCiAgICAi44Of44ON44Op44Or5YiG44Gu44Ki44Or44Kr44Oq5bqmIiwgIuODnuOCsOODjeOCt+OCpuODoCIsICLlhajjg5Xjgqfjg47jg7zjg6vpoZ4iLCAi44OV44Op44OQ44OO44Kk44OJIiwKICAgICLpnZ7jg5Xjg6njg5Djg47jgqTjg4njg5Xjgqfjg47jg7zjg6vpoZ4iLCAi44OX44Ot44Ki44Oz44OI44K344Ki44OL44OzIiwgIuiJsuOBruW8t+OBlSIsICLoibLnm7giLAogICAgIk9EMjgwL09EMzE15YCkIiwgIuODl+ODreODquODsyIKICApCgpkZiA8LSByZWFkX2NzdigKICAiaHR0cHM6Ly9hcmNoaXZlLmljcy51Y2kuZWR1L21sL21hY2hpbmUtbGVhcm5pbmctZGF0YWJhc2VzL3dpbmUvd2luZS5kYXRhIiwKICBjb2xfbmFtZXMgPSB2X25hbWVzLAogIGNvbF90eXBlcyA9ICJmIgogICkgfD4KICBtdXRhdGUoYWNyb3NzKHdoZXJlKGlzLm51bWVyaWMpLCBcKHgpIHNjYWxlKHgpKSkgfD4gI+aomea6luWMlgogIHJvd2lkX3RvX2NvbHVtbigpIHw+CiAgcGl2b3RfbG9uZ2VyKCFjKHJvd2lkLCDjg5bjg4njgqbjga7lk4HnqK4pKSB8PgogIG11dGF0ZShuYW1lID0gZmFjdG9yKG5hbWUsIGxldmVscyA9IHJldih2X25hbWVzKSkpCgpqZXQuY29sb3JzIDwtIGNvbG9yUmFtcFBhbGV0dGUoYygiIzAwMDA3RiIsICJibHVlIiwgIiMwMDdGRkYiLCAiY3lhbiIsICIjN0ZGRjdGIiwgInllbGxvdyIsICIjRkY3RjAwIiwgInJlZCIsICIjN0YwMDAwIikpCgpkZiB8PgogIGdncGxvdChhZXMoeCA9IHJvd2lkLCB5ID0gbmFtZSwgZmlsbCA9IHZhbHVlKSkgKwogIGdlb21fdGlsZSgpICsKICBmYWNldF93cmFwKHZhcnMo44OW44OJ44Km44Gu5ZOB56iuKSwgc2NhbGVzID0gImZyZWVfeCIpICsgCiAgc2NhbGVfZmlsbF9ncmFkaWVudG4oY29sb3VycyA9IGpldC5jb2xvcnMoMTAwKSkgKwogIGxhYnMoeCA9ICLjg6/jgqTjg7Ppipjmn4Tnlarlj7ciLCB5ID0gIiIsIHRpdGxlID0gIuOCq+ODqeODvOOCs+ODvOODieOBp+WApOOCkuihqOePvuOBmeOCiyIpCgpgYGAKCiMjIyA0LjEuNSDlkITlgIvkvZPjga7ooYzli5XmmYLns7vliJfjgpLlj6/oppbljJbjgZnjgosKCmBgYHtyIGZpZy5oZWlnaHQ9MTIsIGZpZy53aWR0aD02LCBtZXNzYWdlPUZBTFNFLCB3YXJuaW5nPUZBTFNFfQpsaWJyYXJ5KGNvbmZsaWN0ZWQpCmxpYnJhcnkodGlkeXZlcnNlKQoKZGYgPC0gcmVhZF9jc3YoCiAgImh0dHBzOi8vcmF3LmdpdGh1YnVzZXJjb250ZW50LmNvbS90a0V6YWtpL2RhdGFfdmlzdWFsaXphdGlvbi9tYWluLzQlRTclQUIlQTAvZGF0YS9iZWhhdmlvcl9kYXRhLmNzdiIKICApIHw+CiAgbXV0YXRlKFRpbWUgPSBUaW1lIC8gMzYwMCkgIHw+ICMgVGltZeWIl+OCkuenkuOBi+OCieaZgumWk+OBq+WkieaPmwogIHBpdm90X2xvbmdlcighVGltZSkgfD4KICBtdXRhdGUoCiAgICB2YWx1ZSA9IGNhc2Vfd2hlbigKICAgICAgdmFsdWUgPT0gIkdhcmJhZ2UiIH4gIuOCtOODn+aNqOOBpuWgtCIsCiAgICAgIHZhbHVlID09ICJOZXN0IiB+ICLlr53lrqQiLAogICAgICB2YWx1ZSA9PSAiT3RoZXIiIH4gIuS4gOiIrOOBrumDqOWxiyIsCiAgICAgIHZhbHVlID09ICJUb2lsZXQiIH4gIuODiOOCpOODrCIKICAgICAgKSB8PgogICAgICBmYWN0b3IobGV2ZWxzID0gYygi44K044Of5o2o44Gm5aC0IiwgIuODiOOCpOODrCIsICLlr53lrqQiLCAi5LiA6Iis44Gu6YOo5bGLIikpCiAgICApIAoKZGYgfD4KICBnZ3Bsb3QoYWVzKHggPW5hbWUgLCB5ID0gVGltZSwgZmlsbCA9IHZhbHVlKSkgKwogIGdlb21fdGlsZSgpICsKICBzY2FsZV95X3JldmVyc2UoKSArCiAgc2NhbGVfZmlsbF9icmV3ZXIocGFsZXR0ZSA9ICJTZXQxIikgKwogIGxhYnModGl0bGUgPSAi44OS44O844OI44Oe44OD44OX44Gr44KI44KL6KGM5YuV5pmC57O75YiX44Gu5Y+v6KaW5YyWIiwgeCA9ICLlgIvkvZMiLCB5ID0gIuaZgumWk1toXSIpCmBgYAoKIyMjIDQuMS42IDHlgIvkvZPjga7lkITooYzli5Xjga7lj6/oppbljJYKCmBgYHtyIGZpZy5oZWlnaHQ9MTIsIGZpZy53aWR0aD02LCBtZXNzYWdlPUZBTFNFLCB3YXJuaW5nPUZBTFNFfQpsaWJyYXJ5KGNvbmZsaWN0ZWQpCmxpYnJhcnkodGlkeXZlcnNlKQpsaWJyYXJ5KHBhdGNod29yaykKCiMgQ1NW44OH44O844K/44KS6Kqt44G/6L6844KACmRmIDwtIHJlYWRfY3N2KAogICJodHRwczovL3Jhdy5naXRodWJ1c2VyY29udGVudC5jb20vdGtFemFraS9kYXRhX3Zpc3VhbGl6YXRpb24vbWFpbi80JUU3JUFCJUEwL2RhdGEvYmVoYXZpb3JfZGF0YS5jc3YiCikgfD4KICBtdXRhdGUoVGltZSA9IFRpbWUgLyAzNjAwKSAgfD4gIyBUaW1l5YiX44KS56eS44GL44KJ5pmC6ZaT44Gr5aSJ5o+bCiAgcGl2b3RfbG9uZ2VyKCFUaW1lKSB8PgogIG11dGF0ZSgKICAgIHZhbHVlID0gY2FzZV93aGVuKAogICAgICB2YWx1ZSA9PSAiR2FyYmFnZSIgfiAi44K044Of5o2o44Gm5aC0IiwKICAgICAgdmFsdWUgPT0gIk5lc3QiIH4gIuWvneWupCIsCiAgICAgIHZhbHVlID09ICJPdGhlciIgfiAi5LiA6Iis44Gu6YOo5bGLIiwKICAgICAgdmFsdWUgPT0gIlRvaWxldCIgfiAi44OI44Kk44OsIgogICAgKSB8PgogICAgICBmYWN0b3IobGV2ZWxzID0gcmV2KGMoIuOCtOODn+aNqOOBpuWgtCIsICLjg4jjgqTjg6wiLCAi5a+d5a6kIiwgIuS4gOiIrOOBrumDqOWxiyIpKSkKICApCgojIDHlgIvkvZMoSinjga7jg4fjg7zjgr8KZGZfaiA8LSBkZiB8PgogIGRwbHlyOjpmaWx0ZXIobmFtZSA9PSAiSiIpIHw+IAogIGRwbHlyOjpzZWxlY3QoIW5hbWUpIHw+CiAgbXV0YXRlKGFjdGlvbiA9ICIxIikKCnAxIDwtIGRmX2ogfD4KICBnZ3Bsb3QoYWVzKHggPSB2YWx1ZSwgeSA9IFRpbWUsIGZpbGwgPSB2YWx1ZSkpICsKICBnZW9tX3RpbGUoKSArCiAgc2NhbGVfeV9yZXZlcnNlKCkgKwogIGxhYnMoeCA9ICIiLCB5ID0gIuaZgumWk1toXSIpICsKICBzY2FsZV9maWxsX2JyZXdlcihwYWxldHRlID0gIlNldDEiKSArCiAgdGhlbWUoCiAgICBsZWdlbmQucG9zaXRpb249Im5vbmUiLAogICAgYXNwZWN0LnJhdGlvID0gNCAvIDEuNQogICAgKQoKcDIgPC0gZGZfaiB8PgogIGRwbHlyOjpmaWx0ZXIoVGltZSA+PSAxMywgVGltZSA8PSAxNikgfD4KICBnZ3Bsb3QoYWVzKHggPSB2YWx1ZSwgeSA9IFRpbWUsIGZpbGwgPSB2YWx1ZSkpICsKICBnZW9tX3RpbGUoKSArCiAgc2NhbGVfeV9yZXZlcnNlKCkgKwogIGxhYnMoeCA9ICIiLCB5ID0gIuaZgumWk1toXSIpICsKICBzY2FsZV9maWxsX2JyZXdlcihwYWxldHRlID0gIlNldDEiKSArCiAgdGhlbWUoCiAgICBsZWdlbmQucG9zaXRpb249Im5vbmUiLAogICAgYXNwZWN0LnJhdGlvID0gNCAvIDEuNQogICkKCnAxICsgcDIKYGBgCgojIyMgNC4yLjEg6Zai5L+C44OH44O844K/44Gu44OS44O844OI44Oe44OD44OX44Gr44KI44KL5Y+v6KaW5YyWCgpgYGB7ciBtZXNzYWdlPUZBTFNFLCB3YXJuaW5nPUZBTFNFfQpsaWJyYXJ5KGNvbmZsaWN0ZWQpCmxpYnJhcnkodGlkeXZlcnNlKSAKbGlicmFyeShwYXRjaHdvcmspCgojIOWFseiRl+ODh+ODvOOCvwpyZXNlYXJjaGVycyA8LSBjKCJBIiwgIkIiLCAiQyIsICJEIiwgIkUiLCAiRiIsICJHIiwgIkgiLCAiSSIsICJKIikKY29sbGFib3JhdGlvbiA8LSBtYXRyaXgoCiAgYygKICAgIE5BLCAxLCAxLCAwLCAwLCAwLCAwLCAwLCAwLCAxLAogICAgMSwgTkEsIDAsIDEsIDEsIDEsIDAsIDAsIDAsIDEsCiAgICAxLCAwLCBOQSwgMCwgMCwgMCwgMSwgMSwgMSwgMCwKICAgIDAsIDEsIDAsIE5BLCAwLCAwLCAwLCAwLCAwLCAwLAogICAgMCwgMSwgMCwgMCwgTkEsIDAsIDAsIDAsIDAsIDAsCiAgICAwLCAxLCAwLCAwLCAwLCBOQSwgMCwgMCwgMCwgMCwKICAgIDAsIDAsIDEsIDAsIDAsIDAsIE5BLCAwLCAwLCAwLAogICAgMCwgMCwgMSwgMCwgMCwgMCwgMCwgTkEsIDAsIDAsCiAgICAwLCAwLCAxLCAwLCAwLCAwLCAwLCAwLCBOQSwgMCwKICAgIDEsIDEsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIE5BCiAgICApLAogIG5yb3c9MTAsCiAgZGltbmFtZXMgPSBsaXN0KHJlc2VhcmNoZXJzLCByZXNlYXJjaGVycykKICApCgpwMSA8LSBjb2xsYWJvcmF0aW9uIHw+CiAgYXMuZGF0YS5mcmFtZSgpIHw+CiAgcm93bmFtZXNfdG9fY29sdW1uKCkgfD4KICBwaXZvdF9sb25nZXIoIXJvd25hbWUpIHw+CiAgbXV0YXRlKAogICAgdmFsdWUgPSBmYWN0b3IodmFsdWUpLAogICAgbmFtZSA9IGZhY3RvcihuYW1lLCBsZXZlbHMgPSByZXYoTEVUVEVSU1sxOjEwXSkpCiAgICApIHw+CiAgZ2dwbG90KGFlcyh4ID0gcm93bmFtZSwgeSA9IG5hbWUsIGZpbGwgPSB2YWx1ZSwgbGFiZWwgPSB2YWx1ZSkpICsKICBnZW9tX3RpbGUoKSArCiAgZ2VvbV90ZXh0KCkgKwogIHNjYWxlX2ZpbGxfaHVlKG5hbWUgPSAiIiwgbGFiZWxzID0gYygiMCIgPSAi5YWx6JGX44Gq44GXIiwgIjEiID0i5YWx6JGX44GC44KKIikpICsKICBsYWJzKHRpdGxlID0gIuWFseiRl+mWouS/guOBruacieeEoSIsIHggPSAiIiwgeSA9ICIiKSArCiAgdGhlbWUoYXNwZWN0LnJhdGlvID0gMSkKCiMg44GT44GT44Gv44KC44GG44Gh44KH44Gj44Go44K544Oe44O844OI44Gr5pu444GR44Gq44GE44GL77yfCnNldC5zZWVkKDApCnYwIDwtIHJ1bmlmKG4gPSAoMTAwIC0xMCkvMiwgbWluID0gMC4wLCBtYXggPSAwLjUpIHw+IHJvdW5kKDIpCnYxIDwtIHJ1bmlmKG4gPSAoMTAwIC0xMCkvMiwgbWluID0gMC41LCBtYXggPSAxLjApIHw+IHJvdW5kKDIpCmNvbGxhYm9yYXRpb25fc2NvcmUgPC0gY29sbGFib3JhdGlvbgpjb2xsYWJvcmF0aW9uX3Njb3JlW3VwcGVyLnRyaShjb2xsYWJvcmF0aW9uX3Njb3JlKV0gPC0KICBpZl9lbHNlKGNvbGxhYm9yYXRpb25bbG93ZXIudHJpKGNvbGxhYm9yYXRpb24pXT09IDEsIHYxLCB2MCkgCmNvbGxhYm9yYXRpb25fc2NvcmUgPC0gdChjb2xsYWJvcmF0aW9uX3Njb3JlKQpjb2xsYWJvcmF0aW9uX3Njb3JlW3VwcGVyLnRyaShjb2xsYWJvcmF0aW9uX3Njb3JlKV0gPC0KICBpZl9lbHNlKGNvbGxhYm9yYXRpb25bbG93ZXIudHJpKGNvbGxhYm9yYXRpb24pXT09IDEsIHYxLCB2MCkKCmpldC5jb2xvcnMgPC0gY29sb3JSYW1wUGFsZXR0ZShjKCIjMDAwMDdGIiwgImJsdWUiLCAiIzAwN0ZGRiIsICJjeWFuIiwgIiM3RkZGN0YiLCAieWVsbG93IiwgIiNGRjdGMDAiLCAicmVkIiwgIiM3RjAwMDAiKSkKCnAyIDwtIGNvbGxhYm9yYXRpb25fc2NvcmUgfD4KICBhcy5kYXRhLmZyYW1lKCkgfD4KICByb3duYW1lc190b19jb2x1bW4oKSB8PgogIHBpdm90X2xvbmdlcighcm93bmFtZSkgfD4KICBtdXRhdGUobmFtZSA9IGZhY3RvcihuYW1lLCBsZXZlbHMgPSByZXYoTEVUVEVSU1sxOjEwXSkpKSB8PgogIGdncGxvdChhZXMoeCA9IHJvd25hbWUsIHkgPSBuYW1lLCBmaWxsID0gdmFsdWUsIGxhYmVsID0gdmFsdWUpKSArCiAgZ2VvbV90aWxlKCkgKwogIGdlb21fdGV4dChzaXplID0gMikgKwogIGxhYnModGl0bGUgPSAi56CU56m244Gu6IiI5ZGz44Gu6aGe5Ly85bqmIiwgeCA9ICIiLCB5ID0gIiIpICsKICB0aGVtZShhc3BlY3QucmF0aW8gPSAxKSArCiAgc2NhbGVfZmlsbF9ncmFkaWVudG4oY29sb3VycyA9IGpldC5jb2xvcnMoMTAwKSkKCnAxICsgcDIKYGBgCgojIyMgNC4yLjIg44ON44OD44OI44Ov44O844Kv44Gr44KI44KL6Zai5L+C44OH44O844K/44Gu5Y+v6KaW5YyWCgrjgZPjgZPjga9nZ3JhcGjjgafmm7jjgY3nm7TjgZnjgYvvvJ8KCmBgYHtyIG1lc3NhZ2U9RkFMU0UsIHdhcm5pbmc9RkFMU0V9CmxpYnJhcnkoY29uZmxpY3RlZCkKbGlicmFyeSh0aWR5dmVyc2UpCmxpYnJhcnkoaWdyYXBoKQoKIyDlhbHokZfjg4fjg7zjgr8KcmVzZWFyY2hlcnMgPC0gYygiQSIsICJCIiwgIkMiLCAiRCIsICJFIiwgIkYiLCAiRyIsICJIIiwgIkkiLCAiSiIpCmNvbGxhYm9yYXRpb24gPC0gbWF0cml4KAogIGMoCiAgICBOQSwgMSwgMSwgMCwgMCwgMCwgMCwgMCwgMCwgMSwKICAgIDEsIE5BLCAwLCAxLCAxLCAxLCAwLCAwLCAwLCAxLAogICAgMSwgMCwgTkEsIDAsIDAsIDAsIDEsIDEsIDEsIDAsCiAgICAwLCAxLCAwLCBOQSwgMCwgMCwgMCwgMCwgMCwgMCwKICAgIDAsIDEsIDAsIDAsIE5BLCAwLCAwLCAwLCAwLCAwLAogICAgMCwgMSwgMCwgMCwgMCwgTkEsIDAsIDAsIDAsIDAsCiAgICAwLCAwLCAxLCAwLCAwLCAwLCBOQSwgMCwgMCwgMCwKICAgIDAsIDAsIDEsIDAsIDAsIDAsIDAsIE5BLCAwLCAwLAogICAgMCwgMCwgMSwgMCwgMCwgMCwgMCwgMCwgTkEsIDAsCiAgICAxLCAxLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCBOQQogICksCiAgbnJvdz0xMCwKICBkaW1uYW1lcyA9IGxpc3QocmVzZWFyY2hlcnMsIHJlc2VhcmNoZXJzKQopCgojIOeglOeptuOBruiIiOWRs+OBrumhnuS8vOW6pgpzZXQuc2VlZCgwKQp2MCA8LSBydW5pZihuID0gKDEwMCAtMTApLzIsIG1pbiA9IDAuMCwgbWF4ID0gMC41KSB8PiByb3VuZCgyKQp2MSA8LSBydW5pZihuID0gKDEwMCAtMTApLzIsIG1pbiA9IDAuNSwgbWF4ID0gMS4wKSB8PiByb3VuZCgyKQpjb2xsYWJvcmF0aW9uX3Njb3JlIDwtIGNvbGxhYm9yYXRpb24KY29sbGFib3JhdGlvbl9zY29yZVt1cHBlci50cmkoY29sbGFib3JhdGlvbl9zY29yZSldIDwtCiAgaWZfZWxzZShjb2xsYWJvcmF0aW9uW2xvd2VyLnRyaShjb2xsYWJvcmF0aW9uKV09PSAxLCB2MSwgdjApIApjb2xsYWJvcmF0aW9uX3Njb3JlIDwtCiAgdChjb2xsYWJvcmF0aW9uX3Njb3JlKQpjb2xsYWJvcmF0aW9uX3Njb3JlW3VwcGVyLnRyaShjb2xsYWJvcmF0aW9uX3Njb3JlKV0gPC0KICBpZl9lbHNlKGNvbGxhYm9yYXRpb25bbG93ZXIudHJpKGNvbGxhYm9yYXRpb24pXT09IDEsIHYxLCB2MCkKCiMg5YWx6JGX44ON44OD44OI44Ov44O844KvCmRpYWcoY29sbGFib3JhdGlvbikgPC0gMApjb2xsYWJvX2cgPC0gY29sbGFib3JhdGlvbiB8PgogIGdyYXBoX2Zyb21fYWRqYWNlbmN5X21hdHJpeChtb2RlID0gInVuZGlyZWN0ZWQiKQoKc2V0LnNlZWQoMCkKCnBhcihtZnJvdyA9IGMoMiwgMiksIG1hciA9IGMoMCwwLDAsMCkpCgpjb2xsYWJvX2cgfD4KICBwbG90KGxheW91dCA9IGxheW91dF9pbl9jaXJjbGUpCgpjb2xsYWJvX2cgfD4KICBwbG90KCkKCiMg6aGe5Ly85bqm44ON44OD44OI44Ov44O844KvCmRpYWcoY29sbGFib3JhdGlvbl9zY29yZSkgPC0gMApzY29yZV9nIDwtIGNvbGxhYm9yYXRpb25fc2NvcmUgfD4KICBncmFwaF9mcm9tX2FkamFjZW5jeV9tYXRyaXgobW9kZSA9ICJ1bmRpcmVjdGVkIiwgd2VpZ2h0ZWQgPSBUUlVFKQoKamV0LmNvbG9ycyA8LSBjb2xvclJhbXBQYWxldHRlKGMoIiMwMDAwN0YiLCAiYmx1ZSIsICIjMDA3RkZGIiwgImN5YW4iLCAiIzdGRkY3RiIsICJ5ZWxsb3ciLCAiI0ZGN0YwMCIsICJyZWQiLCAiIzdGMDAwMCIpKQpjb2xfcCA8LSByb3VuZCgoRShzY29yZV9nKSR3ZWlnaHQgLyBtYXgoRShzY29yZV9nKSR3ZWlnaHQpKSAqIDEwMCwgMCkKCnNldC5zZWVkKDApCgpjb2xsYWJvX2cgfD4KICBwbG90KAogICAgbGF5b3V0ID0gbGF5b3V0X2luX2NpcmNsZSwKICAgIGVkZ2Uud2lkdGggPSBFKHNjb3JlX2cpJHdlaWdodCAqIDEwLAogICAgZWRnZS5jb2xvciA9IGpldC5jb2xvcnMoMTAwKVtjb2xfcF0KICAgICkKCnNjb3JlX2cgfD4KICBwbG90KAogICAgZWRnZS53aWR0aCA9IEUoc2NvcmVfZykkd2VpZ2h0ICogMTAsCiAgICBlZGdlLmNvbG9yID0gamV0LmNvbG9ycygxMDApW2NvbF9wXQogICAgKQoKcGFyKG1mcm93ID0gYygxLCAxKSwgbWFyID0gYyg1LjEsIDQuMSwgNC4xLCAyLjEpKQpgYGAKCiMjIyMgNC4yLjPjgIDmjIflsI7plqLkv4Ljga7lj6/oppbljJYKCiMjIyMjIDQuMi4zLjEKCmBgYHtyIG1lc3NhZ2U9RkFMU0UsIHdhcm5pbmc9RkFMU0V9CmxpYnJhcnkoY29uZmxpY3RlZCkKbGlicmFyeSh0aWR5dmVyc2UpCgojIOeglOeptuiAheODquOCueODiApyZXNlYXJjaGVycyA8LSBjKCJBIiwgIkIiLCAiQyIsICJEIiwgIkUiLCAiRiIsICJHIiwgIkgiLCAiSSIsICJKIikKCiMg5YWx6JGX44OH44O844K/CmNvbGxhYm9yYXRpb24gPC0gbWF0cml4KAogIGMoCiAgICBOQSwgMSwgMSwgMCwgMCwgMCwgMCwgMCwgMCwgMSwKICAgIDAsIE5BLCAwLCAxLCAxLCAxLCAwLCAwLCAwLCAwLAogICAgMCwgMCwgTkEsIDAsIDAsIDAsIDEsIDEsIDEsIDAsCiAgICAwLCAwLCAwLCBOQSwgMCwgMCwgMCwgMCwgMCwgMCwKICAgIDAsIDAsIDAsIDAsIE5BLCAwLCAwLCAwLCAwLCAwLAogICAgMCwgMCwgMCwgMCwgMCwgTkEsIDAsIDAsIDAsIDAsCiAgICAwLCAwLCAwLCAwLCAwLCAwLCBOQSwgMCwgMCwgMCwKICAgIDAsIDAsIDAsIDAsIDAsIDAsIDAsIE5BLCAwLCAwLAogICAgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgTkEsIDAsCiAgICAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCBOQQogICAgKSwKICBucm93ID0gMTAsCiAgZGltbmFtZXMgPSBsaXN0KHJlc2VhcmNoZXJzLCByZXNlYXJjaGVycykKICApCgojIOWFseiRl+ODjeODg+ODiOODr+ODvOOCrwpjb2xsYWJvcmF0aW9uIHw+CiAgYXMuZGF0YS5mcmFtZSgpIHw+CiAgcm93bmFtZXNfdG9fY29sdW1uKCkgfD4KICBwaXZvdF9sb25nZXIoIXJvd25hbWUpIHw+CiAgbXV0YXRlKAogICAgdmFsdWUgPSBmYWN0b3IodmFsdWUpLAogICAgbmFtZSA9IGZhY3RvcihuYW1lLCBsZXZlbHMgPSByZXYoTEVUVEVSU1sxOjEwXSkpCiAgICApIHw+CiAgZ2dwbG90KGFlcyh4ID0gcm93bmFtZSwgeSA9IG5hbWUsIGZpbGwgPSB2YWx1ZSwgbGFiZWwgPSB2YWx1ZSkpICsKICBnZW9tX3RpbGUoKSArCiAgZ2VvbV90ZXh0KCkgKwogIHNjYWxlX2ZpbGxfaHVlKG5hbWUgPSAiIiwgbGFiZWxzID0gYygiMCIgPSAi5oyH5bCO6Zai5L+C44Gq44GXIiwgIjEiID0i5oyH5bCO6Zai5L+C44GC44KKIikpICsKICBsYWJzKHRpdGxlID0gIumao+aOpeihjOWIl+ihqOekuiIsIHggPSAi5oyH5bCO44GV44KM44Gf56CU56m26ICFIiwgeSA9ICLmjIflsI7jgZfjgZ/noJTnqbbogIUiKSArCiAgdGhlbWUoYXNwZWN0LnJhdGlvID0gMSkKYGBgCgojIyMjIyA0LjIuMy4yCgpgYGB7ciBtZXNzYWdlPUZBTFNFLCB3YXJuaW5nPUZBTFNFfQpsaWJyYXJ5KGNvbmZsaWN0ZWQpCmxpYnJhcnkodGlkeXZlcnNlKQpsaWJyYXJ5KGlncmFwaCkKCiMg56CU56m26ICF44Oq44K544OICnJlc2VhcmNoZXJzIDwtIGMoIkEiLCAiQiIsICJDIiwgIkQiLCAiRSIsICJGIiwgIkciLCAiSCIsICJJIiwgIkoiKQoKIyDlhbHokZfjg4fjg7zjgr8KY29sbGFib3JhdGlvbiA8LSBtYXRyaXgoCiAgYygKICAgIE5BLCAxLCAxLCAwLCAwLCAwLCAwLCAwLCAwLCAxLAogICAgMCwgTkEsIDAsIDEsIDEsIDEsIDAsIDAsIDAsIDAsCiAgICAwLCAwLCBOQSwgMCwgMCwgMCwgMSwgMSwgMSwgMCwKICAgIDAsIDAsIDAsIE5BLCAwLCAwLCAwLCAwLCAwLCAwLAogICAgMCwgMCwgMCwgMCwgTkEsIDAsIDAsIDAsIDAsIDAsCiAgICAwLCAwLCAwLCAwLCAwLCBOQSwgMCwgMCwgMCwgMCwKICAgIDAsIDAsIDAsIDAsIDAsIDAsIE5BLCAwLCAwLCAwLAogICAgMCwgMCwgMCwgMCwgMCwgMCwgMCwgTkEsIDAsIDAsCiAgICAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCBOQSwgMCwKICAgIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIE5BCiAgICApLAogIG5yb3cgPSAxMCwKICBkaW1uYW1lcyA9IGxpc3QocmVzZWFyY2hlcnMsIHJlc2VhcmNoZXJzKQogICkKCmRpYWcoY29sbGFib3JhdGlvbikgPC0gMAoKcGFyKG1hciA9IGMoMCwwLDAsMCkpCgpjb2xsYWJvcmF0aW9uIHw+CiAgdCgpIHw+CiAgZ3JhcGhfZnJvbV9hZGphY2VuY3lfbWF0cml4KG1vZGUgPSAiZGlyZWN0ZWQiKSB8PgogIHBsb3QobGF5b3V0ID0gbGF5b3V0X2FzX3RyZWUpCgpwYXIobWFyID0gYyg1LjEsIDQuMSwgNC4xLCAyLjEpKQpgYGAKCiMjIyA0LjIuNCDmp5jjgIXjgarjg6zjgqTjgqLjgqbjg4jjgavjgojjgovjg43jg4Pjg4jjg6/jg7zjgq/mj4/nlLsKCmNpcmNv44Os44Kk44Ki44Km44OI44GMaWdyYXBo44Gr44Gv54Sh44GE44KI44GG44Gq44Gu44GnTURT44Os44Kk44Ki44Km44OI44Gn5Luj55So44CCCgpgYGB7ciBtZXNzYWdlPUZBTFNFLCB3YXJuaW5nPUZBTFNFfQpsaWJyYXJ5KGNvbmZsaWN0ZWQpCmxpYnJhcnkodGlkeXZlcnNlKQpsaWJyYXJ5KGlncmFwaCkKCnNldC5zZWVkKDApCkdfZXIgPC0gZXJkb3MucmVueWkuZ2FtZSgzMCwgMC4yKQpHX3dzIDwtIHdhdHRzLnN0cm9nYXR6LmdhbWUoMSwgMzAsIDUsIDAuMSkKR19iYSA8LSBiYXJhYmFzaS5nYW1lKDMwLCAxKQoKRXJkb3NSIDwtIGFzX2FkamFjZW5jeV9tYXRyaXgoR19lciwgc3BhcnNlID0gRkFMU0UpCldhdHRzU3Ryb2dhdHogPC0gYXNfYWRqYWNlbmN5X21hdHJpeChHX3dzLCBzcGFyc2UgPSBGQUxTRSkKQmFyYWJhc2lBbGJlcnQgPC0gYXNfYWRqYWNlbmN5X21hdHJpeChHX2JhLCBzcGFyc2UgPSBGQUxTRSkKCm5ldDEgPC0gZ3JhcGhfZnJvbV9hZGphY2VuY3lfbWF0cml4KEVyZG9zUiwgbW9kZSA9ICJtYXgiKQpuZXQyIDwtIGdyYXBoX2Zyb21fYWRqYWNlbmN5X21hdHJpeChXYXR0c1N0cm9nYXR6LCBtb2RlID0gIm1heCIpCm5ldDMgPC0gZ3JhcGhfZnJvbV9hZGphY2VuY3lfbWF0cml4KEJhcmFiYXNpQWxiZXJ0LCBtb2RlID0gIm1heCIpCgpwYXIobWZyb3cgPSBjKDMsMyksIG1hciA9IGMoMCwwLDEsMCkpCnBsb3QobmV0MSwgbGF5b3V0ID0gbGF5b3V0X2luX2NpcmNsZSwKICAgICBtYWluID0gIkVyZG9zLVJleW5pOiBDaXJjdWxhciBMYXlvdXQiLCB2ZXJ0ZXguc2l6ZSA9IDksIHZlcnRleC5sYWJlbD1OQSwgKQpwbG90KG5ldDIsIGxheW91dCA9IGxheW91dF9pbl9jaXJjbGUsCiAgICAgbWFpbiA9ICJXYXR0cy1TdHJvZ2F0ejogQ2lyY3VsYXIgTGF5b3V0IiwgdmVydGV4LnNpemUgPSA5LCB2ZXJ0ZXgubGFiZWw9TkEpCnBsb3QobmV0MywgbGF5b3V0ID0gbGF5b3V0X2luX2NpcmNsZSwKICAgICBtYWluID0gIkJhcmFiYXNpLUFsYmVydDogQ2lyY3VsYXIgTGF5b3V0IiwgdmVydGV4LnNpemUgPSA5LCB2ZXJ0ZXgubGFiZWw9TkEpCgpwbG90KG5ldDEsIGxheW91dCA9IGxheW91dF93aXRoX21kcywKICAgICBtYWluID0gIkVyZG9zLVJleW5pOiBNRFMgTGF5b3V0IiwgdmVydGV4LnNpemUgPSA5LCB2ZXJ0ZXgubGFiZWw9TkEpCnBsb3QobmV0MiwgbGF5b3V0ID0gbGF5b3V0X3dpdGhfbWRzLAogICAgIG1haW4gPSAiV2F0dHMtU3Ryb2dhdHo6IE1EUyBMYXlvdXQiLCB2ZXJ0ZXguc2l6ZSA9IDksIHZlcnRleC5sYWJlbD1OQSkKcGxvdChuZXQzLCBsYXlvdXQgPSBsYXlvdXRfd2l0aF9tZHMsCiAgICAgbWFpbiA9ICJCYXJhYmFzaS1BbGJlcnQ6IE1EUyBMYXlvdXQiLCB2ZXJ0ZXguc2l6ZSA9IDksIHZlcnRleC5sYWJlbD1OQSkKCnBsb3QobmV0MSwgbGF5b3V0ID0gbGF5b3V0X3dpdGhfa2sobmV0MSksCiAgICAgbWFpbiA9ICJFcmRvcy1SZXluaTogS0sgTGF5b3V0IiwgdmVydGV4LnNpemUgPSA5LCB2ZXJ0ZXgubGFiZWw9TkEpCnBsb3QobmV0MiwgbGF5b3V0ID0gbGF5b3V0X3dpdGhfa2sobmV0MiksCiAgICAgbWFpbiA9ICJXYXR0cy1TdHJvZ2F0ejogS0sgTGF5b3V0IiwgdmVydGV4LnNpemUgPSA5LCB2ZXJ0ZXgubGFiZWw9TkEpCnBsb3QobmV0MywgbGF5b3V0ID0gbGF5b3V0X3dpdGhfa2sobmV0MyksCiAgICAgbWFpbiA9ICJCYXJhYmFzaS1BbGJlcnQ6IEtLIExheW91dCIsIHZlcnRleC5zaXplID0gOSwgdmVydGV4LmxhYmVsPU5BKQoKcGFyKG1mcm93ID0gYygxLDEpLCBtYXIgPSBjKDUuMSwgNC4xLCA0LjEsIDIuMSkpCmBgYAoKIyMjIDQuMi41IOacieWQkeODjeODg+ODiOODr+ODvOOCr+OBruWPr+imluWMlgoKZG9044GoY2lyY2/jgYznhKHjgYTjga7jgad0cmVlLCBtZHPjgafku6PnlKgKCmBgYHtyIG1lc3NhZ2U9RkFMU0UsIHdhcm5pbmc9RkFMU0V9CmxpYnJhcnkoY29uZmxpY3RlZCkKbGlicmFyeSh0aWR5dmVyc2UpCmxpYnJhcnkoaWdyYXBoKQoKIyDjg6njg7Pjg4Djg6DmnInlkJHjgrDjg6njg5XjgpLnlJ/miJAKc2V0LnNlZWQoMCkKR19kaXJfcmFuZG9tIDwtIHNhbXBsZV9nbm0oMzAsIDgxLCBkaXJlY3RlZCA9IFRSVUUpIAoKIyDpmo7lsaTmp4vpgKDjgpLmjIHjgaTmnInlkJHjgrDjg6njg5XjgpLnlJ/miJAKc2V0LnNlZWQoMCkKR19kaXJfaGllcmFyY2h5IDwtIHNhbXBsZV90cmVlKDMwLCBkaXJlY3RlZCA9IFRSVUUpCgpteV9wbG90IDwtIGZ1bmN0aW9uKGRhdGEsIGxheW91dCl7CiAgcGxvdCgKICAgIGRhdGEsIGxheW91dCA9IGxheW91dCwKICAgIHZlcnRleC5sYWJlbCA9IE5BLAogICAgZWRnZS5hcnJvdy5zaXplID0gMC41CiAgICApCn0KcGFyKG1mcm93ID0gYygzLDIpLCBtYXIgPSBjKDAsMCwwLDApKQpteV9wbG90KEdfZGlyX3JhbmRvbSwgbGF5b3V0X2FzX3RyZWUpCm15X3Bsb3QoR19kaXJfaGllcmFyY2h5LCBsYXlvdXRfYXNfdHJlZSkKbXlfcGxvdChHX2Rpcl9yYW5kb20sIGxheW91dF93aXRoX21kcykKbXlfcGxvdChHX2Rpcl9oaWVyYXJjaHksIGxheW91dF93aXRoX21kcykKbXlfcGxvdChHX2Rpcl9yYW5kb20sIGxheW91dF93aXRoX2trKQpteV9wbG90KEdfZGlyX2hpZXJhcmNoeSwgbGF5b3V0X3dpdGhfa2spCnBhcihtZnJvdyA9IGMoMSwxKSwgbWFyID0gYyg1LjEsIDQuMSwgNC4xLCAyLjEpKQpgYGAKCiMjIyA0LjMuMSDjgq/jg6njgrnjgr/jg7zjg57jg4Pjg5fjgavjgojjgovjg4fjg7zjgr/jga7lj6/oppbljJYKCmBgYHtyIG1lc3NhZ2U9RkFMU0UsIHdhcm5pbmc9RkFMU0V9CmxpYnJhcnkoY29uZmxpY3RlZCkKbGlicmFyeSh0aWR5dmVyc2UpCmxpYnJhcnkocGhlYXRtYXApCgpkZiA8LSByZWFkX2NzdigKICAiaHR0cHM6Ly9hcmNoaXZlLmljcy51Y2kuZWR1L21sL21hY2hpbmUtbGVhcm5pbmctZGF0YWJhc2VzL3dpbmUvd2luZS5kYXRhIiwKICBjb2xfbmFtZXMgPSBjKAogICAgIuODluODieOCpuOBruWTgeeoriIsICLjgqLjg6vjgrPjg7zjg6vluqbmlbAiLCAi44Oq44Oz44K06YW4IiwgIuODn+ODjeODqeODq+WIhiIsIAogICAgIuODn+ODjeODqeODq+WIhuOBruOCouODq+OCq+ODquW6piIsICLjg57jgrDjg43jgrfjgqbjg6AiLCAi5YWo44OV44Kn44OO44O844Or6aGeIiwgIuODleODqeODkOODjuOCpOODiSIsCiAgICAi6Z2e44OV44Op44OQ44OO44Kk44OJ44OV44Kn44OO44O844Or6aGeIiwgIuODl+ODreOCouODs+ODiOOCt+OCouODi+ODsyIsICLoibLjga7lvLfjgZUiLCAi6Imy55u4IiwKICAgICJPRDI4MC9PRDMxNeWApCIsICLjg5fjg63jg6rjg7MiCiAgKSwKICBjb2xfdHlwZXMgPSAiZiIKKSB8PgogIG11dGF0ZShhY3Jvc3Mod2hlcmUoaXMubnVtZXJpYyksIFwoeCkgc2NhbGUoeCkpKSAj5qiZ5rqW5YyWCgpqZXQuY29sb3JzIDwtIGNvbG9yUmFtcFBhbGV0dGUoYygiIzAwMDA3RiIsICJibHVlIiwgIiMwMDdGRkYiLCAiY3lhbiIsICIjN0ZGRjdGIiwgInllbGxvdyIsICIjRkY3RjAwIiwgInJlZCIsICIjN0YwMDAwIikpCgpwaGVhdG1hcCgKICBkZiB8PgogICAgZHBseXI6OnNlbGVjdCgh44OW44OJ44Km44Gu5ZOB56iuKSB8PgogICAgdCgpLAogIGNvbG9yID0gamV0LmNvbG9ycyg1MCksCiAgY2x1c3RlcmluZ19tZXRob2QgPSAid2FyZC5EMiIKICApCmBgYAoKIyMjIDQuMy4zIOanmOOAheOBquOCr+ODqeOCueOCv+ODquODs+OCsOaJi+azlQoKQklSQ0jjgaDjgZHopovjgaTjgYvjgonjgarjgYTjga7jgafnnIHnlaXjgIIKCuOBoeOBquOBv+OBq1Ljgafjga9bbWxiZW5jaF0oaHR0cHM6Ly9xaWl0YS5jb20vcHVycGxlX2pwL2l0ZW1zLzBmMmZjMDRlZmM5M2RjMmExZjhmKeODkeODg+OCseODvOOCuOOBq+ODmeODs+ODgeODnuODvOOCr+eUqOOBruanmOOAheOBquODh+ODvOOCv+OCu+ODg+ODiOOBqOS6uuW3peODh+ODvOOCv+eUn+aIkOeUqOOBrumWouaVsOOBjOeUqOaEj+OBleOCjOOBpuOBhOOBvuOBmeOAggoKYGBge3IgbWVzc2FnZT1GQUxTRSwgd2FybmluZz1GQUxTRSwgY2FjaGUgPSBUUlVFfQpsaWJyYXJ5KGNvbmZsaWN0ZWQpCmxpYnJhcnkodGlkeXZlcnNlKQpsaWJyYXJ5KENsdXN0ZXJSKSAgICMgTWluaUJhdGNoIEtNZWFucwpsaWJyYXJ5KGFwY2x1c3RlcikgICMgQWZmaW5pdHkgUHJvcGFnYXRpb24KbGlicmFyeShtZWFuU2hpZnRSKSAjIE1lYW5TaGlmdApsaWJyYXJ5KHNrbWVhbnMpICAgICMgU3BlY3RyYWwgQ2x1c3RlcmluZwpsaWJyYXJ5KGNsdXN0ZXIpICAgICMgQWdnbG9tZXJhdGl2ZSBDbHVzdGVyaW5nCmxpYnJhcnkoZGJzY2FuKSAgICAgIyBEQlNDQU4sIEhEQlNDQU4sIE9QVElDUywKbGlicmFyeShtY2x1c3QpICAgICAjIEdhdXNzaWFuIE1peHR1cmUKbGlicmFyeShwYXRjaHdvcmspCgojIOODh+ODvOOCv+eUqOaEjwpteV9yZWFkX2NzdiA8LSBmdW5jdGlvbihmaWxlKXsKICByZWFkX2NzdihmaWxlLCBjb2xfbmFtZXMgPSBjKCJ4IiwgInkiLCAiY2xhc3MiKSkgfD4KICAgIG11dGF0ZSggI+aomea6luWMluOBl+OBpuOBiuOBjwogICAgICB4ID0gKHggLSBtZWFuKHgpKS9zZCh4KSwKICAgICAgeSA9ICh5IC0gbWVhbih4KSkvc2QoeCksICAKICAgICAgY2xhc3MgPSBmYWN0b3IoY2xhc3MgKyAxKSkKfQoKIyDlhoblvaLjga7jgq/jg6njgrnjgr8Kbm9pc3lfY2lyY2xlcyA8LSBteV9yZWFkX2NzdigKICAiaHR0cHM6Ly9yYXcuZ2l0aHVidXNlcmNvbnRlbnQuY29tL21vcmltb3Rvb3NhbXUvZGF0YV92aXN1YWxpemF0aW9uL21haW4vZGF0YS9ub2lzeV9jaXJjbGVzLmNzdiIKICApCgojIOaciOWei+OBruOCr+ODqeOCueOCvwpub2lzeV9tb29ucyA8LSBteV9yZWFkX2NzdigKICAiaHR0cHM6Ly9yYXcuZ2l0aHVidXNlcmNvbnRlbnQuY29tL21vcmltb3Rvb3NhbXUvZGF0YV92aXN1YWxpemF0aW9uL21haW4vZGF0YS9ub2lzeV9tb29ucy5jc3YiCiAgKSAgICAgCgojIOato+imj+WIhuW4g+OBq+W+k+OBhuOCr+ODqeOCueOCvwpibG9icyA8LSBteV9yZWFkX2NzdigKICAiaHR0cHM6Ly9yYXcuZ2l0aHVidXNlcmNvbnRlbnQuY29tL21vcmltb3Rvb3NhbXUvZGF0YV92aXN1YWxpemF0aW9uL21haW4vZGF0YS9ibG9icy5jc3YiCiAgKSAgICAKCiMg55Ww5pa55oCn44Gu44GC44KL44OH44O844K/CmFuaXNvIDwtIG15X3JlYWRfY3N2KAogICJodHRwczovL3Jhdy5naXRodWJ1c2VyY29udGVudC5jb20vbW9yaW1vdG9vc2FtdS9kYXRhX3Zpc3VhbGl6YXRpb24vbWFpbi9kYXRhL2FuaXNvLmNzdiIKICApICAgICAgIAoKIyAz44Gk44Gu5q2j6KaP5YiG5biD44Gr5b6T44GG44OH44O844K/CnZhcmllZCA8LSBteV9yZWFkX2NzdigKICAiaHR0cHM6Ly9yYXcuZ2l0aHVidXNlcmNvbnRlbnQuY29tL21vcmltb3Rvb3NhbXUvZGF0YV92aXN1YWxpemF0aW9uL21haW4vZGF0YS92YXJpZWQuY3N2IgogICkgICAgICAgICAgICAgICAKCm4gPC0gNTAwCnNldC5zZWVkKDApCm5vX3N0cnVjdHVyZSA8LSBkYXRhLmZyYW1lKHggPSBydW5pZihuKSwgeSA9IHJ1bmlmKG4pLCBjbGFzcyA9IGZhY3RvcigiMCIpKSMg5qeL6YCg44Gu44Gq44GE44OH44O844K/CgojIOWQhOaJi+azleOBruODqeODg+ODkeODvOmWouaVsOOCkueUqOaEjwojIE1pbmlCYXRjaCBLTWVhbnMKbXlfTWluaUJhdGNoS21lYW5zIDwtIGZ1bmN0aW9uKGRhdGEsIGNsdXN0ZXJfbnVtKSB7CiAgZGF0YV9jbGVhbmVkIDwtIGRhdGFbLCAxOjJdCiAgc3RhcnQgPC0gU3lzLnRpbWUoKQogIGZpdCA8LSBNaW5pQmF0Y2hLbWVhbnMoZGF0YV9jbGVhbmVkLCBjbHVzdGVycyA9IGNsdXN0ZXJfbnVtKQogIHByZWQgPC0gcHJlZGljdChmaXQsIGRhdGFfY2xlYW5lZCkKICBlbmQgPC0gU3lzLnRpbWUoKQogIGRpZmYgPC0gZW5kIC0gc3RhcnQKICBkYXRhJHByZWQgPC0gYXMuZmFjdG9yKHByZWQpCiAgcmV0dXJuKGxpc3QocmVzID0gZGF0YSwgZGlmZiA9IGRpZmYpKQp9CgojIEFmZmluaXR5IFByb3BhZ2F0aW9uCm15X2FwY2x1c3RlciA8LSBmdW5jdGlvbihkYXRhLCBjbHVzdGVyX251bSkgewogIGRhdGFfY2xlYW5lZCA8LSBkYXRhWywgMToyXQogIHN0YXJ0IDwtIFN5cy50aW1lKCkKICBwcmVkIDwtIGFwY2x1c3RlcihzID0gbmVnRGlzdE1hdChyPTIpLCB4ID0gZGF0YV9jbGVhbmVkLCBwID0gLTIwMCwgcSA9IDAuOSkgfD4KICAgIGN1dHJlZShjbHVzdGVyX251bSkgfD4KICAgIGxhYmVscyh0eXBlID0gImVudW0iKQogIGVuZCA8LSBTeXMudGltZSgpCiAgZGlmZiA8LSBlbmQgLSBzdGFydAogIGRhdGEkcHJlZCA8LSBhcy5mYWN0b3IocHJlZCkKICByZXR1cm4obGlzdChyZXMgPSBkYXRhLCBkaWZmID0gZGlmZikpCn0KCiMgTWVhblNoaWZ0Cm15X21lYW5TaGlmdCA8LSBmdW5jdGlvbihkYXRhKSB7CiAgZGF0YV9jbGVhbmVkIDwtIGFzLm1hdHJpeChkYXRhWywgMToyXSkKICBzdGFydCA8LSBTeXMudGltZSgpCiAgcHJlZCA8LSBtZWFuU2hpZnQoZGF0YV9jbGVhbmVkLCBkYXRhX2NsZWFuZWQpJGFzc2lnbm1lbnQKICBlbmQgPC0gU3lzLnRpbWUoKQogIGRpZmYgPC0gZW5kIC0gc3RhcnQKICBkYXRhJHByZWQgPC0gYXMuZmFjdG9yKHByZWQpCiAgcmV0dXJuKGxpc3QocmVzID0gZGF0YSwgZGlmZiA9IGRpZmYpKQp9CgojIFNwZWN0cmFsIENsdXN0ZXJpbmcKbXlfc2ttZWFucyA8LSBmdW5jdGlvbihkYXRhLCBjbHVzdGVyX251bSkgewogIGRhdGFfY2xlYW5lZCA8LSBiYXNlOjphcy5tYXRyaXgoZGF0YVssIDE6Ml0pCiAgc3RhcnQgPC0gU3lzLnRpbWUoKQogIHByZWQgPC0gc2ttZWFucyhkYXRhX2NsZWFuZWQsIGsgPSBjbHVzdGVyX251bSkkY2x1c3RlcgogIGVuZCA8LSBTeXMudGltZSgpCiAgZGlmZiA8LSBlbmQgLSBzdGFydAogIGRhdGEkcHJlZCA8LSBhcy5mYWN0b3IocHJlZCkKICByZXR1cm4obGlzdChyZXMgPSBkYXRhLCBkaWZmID0gZGlmZikpCn0KCiMgV2FyZApteV9oY2x1c3QgPC0gZnVuY3Rpb24oZGF0YSwgY2x1c3Rlcl9udW0pIHsKICBkYXRhX2NsZWFuZWQgPC0gZGF0YVssIDE6Ml0KICBzdGFydCA8LSBTeXMudGltZSgpCiAgcHJlZCA8LSBkYXRhX2NsZWFuZWQgfD4KICAgIHN0YXRzOjpkaXN0KCkgfD4KICAgIGhjbHVzdChtZXRob2QgPSAid2FyZC5EMiIpIHw+CiAgICBjdXRyZWUoayA9IGNsdXN0ZXJfbnVtKQogIGVuZCA8LSBTeXMudGltZSgpCiAgZGlmZiA8LSBlbmQgLSBzdGFydAogIGRhdGEkcHJlZCA8LSBhcy5mYWN0b3IocHJlZCkKICByZXR1cm4obGlzdChyZXMgPSBkYXRhLCBkaWZmID0gZGlmZikpCn0KCiMgQWdnbG9tZXJhdGl2ZSBDbHVzdGVyaW5nCm15X2FnbmVzIDwtIGZ1bmN0aW9uKGRhdGEsIGNsdXN0ZXJfbnVtKSB7CiAgZGF0YV9jbGVhbmVkIDwtIGRhdGFbLCAxOjJdCiAgc3RhcnQgPC0gU3lzLnRpbWUoKQogIHByZWQgPC0gYWduZXMoZGF0YV9jbGVhbmVkKSB8PiBjdXRyZWUoayA9IGNsdXN0ZXJfbnVtKQogIGVuZCA8LSBTeXMudGltZSgpCiAgZGlmZiA8LSBlbmQgLSBzdGFydAogIGRhdGEkcHJlZCA8LSBhcy5mYWN0b3IocHJlZCkKICByZXR1cm4obGlzdChyZXMgPSBkYXRhLCBkaWZmID0gZGlmZikpCn0KCiMgREJTQ0FOCm15X2Ric2NhbiA8LSBmdW5jdGlvbihkYXRhKSB7CiAgZGF0YV9jbGVhbmVkIDwtIGRhdGFbLCAxOjJdCiAgc3RhcnQgPC0gU3lzLnRpbWUoKQogIHByZWQgPC0gZGJzY2FuOjpkYnNjYW4oZGF0YV9jbGVhbmVkLCBlcHMgPSAwLjMpJGNsdXN0ZXIKICBlbmQgPC0gU3lzLnRpbWUoKQogIGRpZmYgPC0gZW5kIC0gc3RhcnQKICBkYXRhJHByZWQgPC0gYXMuZmFjdG9yKHByZWQpCiAgcmV0dXJuKGxpc3QocmVzID0gZGF0YSwgZGlmZiA9IGRpZmYpKQp9CgojIEhEQlNDQU4KbXlfaGRic2NhbiA8LSBmdW5jdGlvbihkYXRhKSB7CiAgZGF0YV9jbGVhbmVkIDwtIGRhdGFbLCAxOjJdCiAgc3RhcnQgPC0gU3lzLnRpbWUoKQogIHByZWQgPC0gZGJzY2FuOjpoZGJzY2FuKGRhdGFfY2xlYW5lZCwgbWluUHRzID0gMTUpJGNsdXN0ZXIKICBlbmQgPC0gU3lzLnRpbWUoKQogIGRpZmYgPC0gZW5kIC0gc3RhcnQKICBkYXRhJHByZWQgPC0gYXMuZmFjdG9yKHByZWQpCiAgcmV0dXJuKGxpc3QocmVzID0gZGF0YSwgZGlmZiA9IGRpZmYpKQp9CgojIE9QVElDUwpteV9vcHRpY3MgPC0gZnVuY3Rpb24oZGF0YSkgewogIGRhdGFfY2xlYW5lZCA8LSBkYXRhWywgMToyXQogIHN0YXJ0IDwtIFN5cy50aW1lKCkKICBwcmVkIDwtIGRic2Nhbjo6b3B0aWNzKGRhdGFfY2xlYW5lZCwgZXBzID0gMC4xLCBtaW5QdHMgPSA3KSB8PgogICAgZXh0cmFjdFhpKHhpID0gMC4wNSkgfD4KICAgIHBsdWNrKCJjbHVzdGVyIikKICBlbmQgPC0gU3lzLnRpbWUoKQogIGRpZmYgPC0gZW5kIC0gc3RhcnQKICBkYXRhJHByZWQgPC0gYXMuZmFjdG9yKHByZWQpCiAgcmV0dXJuKGxpc3QocmVzID0gZGF0YSwgZGlmZiA9IGRpZmYpKQp9CgojIEdhdXNzaWFuIE1peHR1cmUKbXlfTWNsdXN0IDwtIGZ1bmN0aW9uKGRhdGEpIHsKICBkYXRhX2NsZWFuZWQgPC0gZGF0YVssIDE6Ml0KICBzdGFydCA8LSBTeXMudGltZSgpCiAgcHJlZCA8LSBtY2x1c3Q6Ok1jbHVzdChkYXRhX2NsZWFuZWQsIEcgPSAxOjMpJGNsYXNzaWZpY2F0aW9uCiAgZW5kIDwtIFN5cy50aW1lKCkKICBkaWZmIDwtIGVuZCAtIHN0YXJ0CiAgZGF0YSRwcmVkIDwtIGFzLmZhY3RvcihwcmVkKQogIHJldHVybihsaXN0KHJlcyA9IGRhdGEsIGRpZmYgPSBkaWZmKSkKfQoKIyMjIOOCr+ODqeOCueOCv+ODquODs+OCsOWun+ihjApkYXRzIDwtIGxpc3Qobm9pc3lfY2lyY2xlcywgbm9pc3lfbW9vbnMsIHZhcmllZCwgYW5pc28sIGJsb2JzLCBub19zdHJ1Y3R1cmUpCmNudW1zIDwtIGxpc3QoMiwyLDMsMywzLDMpCgpzZXQuc2VlZCgwKQpyZXNfY2x1c3RlcmluZyA8LSBsaXN0KAogIHJlc19NaW5pQmF0Y2hLbWVhbnMgPSBtYXAyKGRhdHMsIGNudW1zLCBcKGRhdHMsIGNudW1zKSBteV9NaW5pQmF0Y2hLbWVhbnMoZGF0cywgY251bXMpKSwKICByZXNfYXBjbHVzdGVyICAgICAgID0gbWFwMihkYXRzLCBjbnVtcywgXChkYXRzLCBjbnVtcykgbXlfYXBjbHVzdGVyKGRhdHMsIGNudW1zKSksCiAgcmVzX21lYW5TaGlmdCAgICAgICA9IHB1cnJyOjptYXAoZGF0cywgXChkYXRzKSBteV9tZWFuU2hpZnQoZGF0cykpLAogIHJlc19za21lYW5zICAgICAgICAgPSBtYXAyKGRhdHMsIGNudW1zLCBcKGRhdHMsIGNudW1zKSBteV9za21lYW5zKGRhdHMsIGNudW1zKSksCiAgcmVzX2hjbHVzdCAgICAgICAgICA9IG1hcDIoZGF0cywgY251bXMsIFwoZGF0cywgY251bXMpIG15X2hjbHVzdChkYXRzLCBjbnVtcykpLAogIHJlc19hZ25lcyAgICAgICAgICAgPSBtYXAyKGRhdHMsIGNudW1zLCBcKGRhdHMsIGNudW1zKSBteV9hZ25lcyhkYXRzLCBjbnVtcykpLAogIHJlc19kYnNjYW4gICAgICAgICAgPSBwdXJycjo6bWFwKGRhdHMsIFwoZGF0cykgbXlfZGJzY2FuKGRhdHMpKSwKICByZXNfaGRic2NhbiAgICAgICAgID0gcHVycnI6Om1hcChkYXRzLCBcKGRhdHMpIG15X2hkYnNjYW4oZGF0cykpLAogIHJlc19vcHRpY3MgICAgICAgICAgPSBwdXJycjo6bWFwKGRhdHMsIFwoZGF0cykgbXlfb3B0aWNzKGRhdHMpKSwKICByZXNfTWNsdXN0ICAgICAgICAgID0gcHVycnI6Om1hcChkYXRzLCBcKGRhdHMpIG15X01jbHVzdChkYXRzKSkKKSAKCiMg5o+P55S755So44Op44OD44OR44O86Zai5pWw44KS55So5oSPCm15X3Bsb3QgPC0gZnVuY3Rpb24ocmVzdWx0KSB7CiAgcmVzdWx0JHJlcyB8PgogICAgZ2dwbG90KGFlcyh4ID0geCwgeSA9IHksIGNvbG9yID0gcHJlZCkpICsKICAgIGdlb21fcG9pbnQoc2l6ZSA9IDEpICsgCiAgICBsYWJzKGNhcHRpb24gPSBwYXN0ZTAocm91bmQocmVzdWx0JGRpZmYsMyksInMiKSkgKwogICAgdGhlbWUoCiAgICAgIGF4aXMudGlja3MgPSBlbGVtZW50X2JsYW5rKCksICAjIHRpY2vjga7nt5rjgpLmtojjgZkKICAgICAgYXhpcy50ZXh0ID0gZWxlbWVudF9ibGFuaygpLCAgICMgdGlja+OBruaVsOWtl+OCkua2iOOBmQogICAgICBheGlzLnRpdGxlID0gZWxlbWVudF9ibGFuaygpLCAgIyDou7jjga7jg6njg5njg6vjgpLmtojjgZkKICAgICAgYXhpcy5saW5lID0gZWxlbWVudF9ibGFuaygpLCAgICMg6Lu444Gu57ea44KS5raI44GZCiAgICAgIGxlZ2VuZC5wb3NpdGlvbj0ibm9uZSIsCiAgICAgIGFzcGVjdC5yYXRpbyA9IDEKICAgICAgKQp9CgpudW1zIDwtIGV4cGFuZF9ncmlkKGQgPSAxOjYsIG0gPSAxOjEwKQpyZXNfcGxvdCA8LSBtYXAyKG51bXMkbSwgbnVtcyRkLCBcKC54LCAueSkgbXlfcGxvdChyZXNfY2x1c3RlcmluZ1tbLnhdXVtbLnldXSkpCgojIOOBk+OBk+OBjOODgOOCteOBhOKApuKApuOCguOBhuOBoeOCh+OBo+OBqOOBqeOBhuOBq+OBi+OBquOCieOBquOBhOOBiwpyZXNfcGxvdFtbMV1dICsgcmVzX3Bsb3RbWzJdXSArcmVzX3Bsb3RbWzNdXSArcmVzX3Bsb3RbWzRdXSArcmVzX3Bsb3RbWzVdXSArcmVzX3Bsb3RbWzZdXSArCiAgcmVzX3Bsb3RbWzddXSArIHJlc19wbG90W1s4XV0gK3Jlc19wbG90W1s5XV0gK3Jlc19wbG90W1sxMF1dICtyZXNfcGxvdFtbMTFdXSArcmVzX3Bsb3RbWzEyXV0gKwogIHJlc19wbG90W1sxM11dICsgcmVzX3Bsb3RbWzE0XV0gK3Jlc19wbG90W1sxNV1dICtyZXNfcGxvdFtbMTZdXSArcmVzX3Bsb3RbWzE3XV0gK3Jlc19wbG90W1sxOF1dICsKICByZXNfcGxvdFtbMTldXSArIHJlc19wbG90W1syMF1dICtyZXNfcGxvdFtbMjFdXSArcmVzX3Bsb3RbWzIyXV0gK3Jlc19wbG90W1syM11dICtyZXNfcGxvdFtbMjRdXSArCiAgcmVzX3Bsb3RbWzI1XV0gKyByZXNfcGxvdFtbMjZdXSArcmVzX3Bsb3RbWzI3XV0gK3Jlc19wbG90W1syOF1dICtyZXNfcGxvdFtbMjldXSArcmVzX3Bsb3RbWzMwXV0gKwogIHJlc19wbG90W1szMV1dICsgcmVzX3Bsb3RbWzMyXV0gK3Jlc19wbG90W1szM11dICtyZXNfcGxvdFtbMzRdXSArcmVzX3Bsb3RbWzM1XV0gK3Jlc19wbG90W1szNl1dICsKICByZXNfcGxvdFtbMzddXSArIHJlc19wbG90W1szOF1dICtyZXNfcGxvdFtbMzldXSArcmVzX3Bsb3RbWzQwXV0gK3Jlc19wbG90W1s0MV1dICtyZXNfcGxvdFtbNDJdXSArCiAgcmVzX3Bsb3RbWzQzXV0gKyByZXNfcGxvdFtbNDRdXSArcmVzX3Bsb3RbWzQ1XV0gK3Jlc19wbG90W1s0Nl1dICtyZXNfcGxvdFtbNDddXSArcmVzX3Bsb3RbWzQ4XV0gKwogIHJlc19wbG90W1s0OV1dICsgcmVzX3Bsb3RbWzUwXV0gK3Jlc19wbG90W1s1MV1dICtyZXNfcGxvdFtbNTJdXSArcmVzX3Bsb3RbWzUzXV0gK3Jlc19wbG90W1s1NF1dICsKICByZXNfcGxvdFtbNTVdXSArIHJlc19wbG90W1s1Nl1dICtyZXNfcGxvdFtbNTddXSArcmVzX3Bsb3RbWzU4XV0gK3Jlc19wbG90W1s1OV1dICtyZXNfcGxvdFtbNjBdXSArCiAgcGxvdF9sYXlvdXQobmNvbCA9IDEwKQpgYGAKCiMjIyA0LjMuNCDlpJrlpInmlbDjgpLjg5rjgqLjg5fjg63jg4Pjg4jjgafopovjgosKCmBgYHtyIGZpZy5oZWlnaHQ9Ny41LCBmaWcud2lkdGg9Ny41LCBtZXNzYWdlPUZBTFNFLCB3YXJuaW5nPUZBTFNFLCBjYWNoZSA9IFRSVUV9CmxpYnJhcnkoY29uZmxpY3RlZCkKbGlicmFyeSh0aWR5dmVyc2UpCmxpYnJhcnkoR0dhbGx5KQoKZGYgPC0gcmVhZF9jc3YoCiAgImh0dHBzOi8vcmF3LmdpdGh1YnVzZXJjb250ZW50LmNvbS9tb3JpbW90b29zYW11L2RhdGFfdmlzdWFsaXphdGlvbi9tYWluL2RhdGEvZGZfNDM0LmNzdiIKICApCgpkZiB8PgogIGdncGFpcnMoKQpgYGAKCiMjIyA0LjMuNSDkuLvmiJDliIbliIbmnpDjga7jgqTjg6Hjg7zjgrgKCmBgYHtyIG1lc3NhZ2U9RkFMU0UsIHdhcm5pbmc9RkFMU0V9CmxpYnJhcnkoY29uZmxpY3RlZCkKbGlicmFyeSh0aWR5dmVyc2UpCmxpYnJhcnkoc2ttZWFucykKbGlicmFyeShHR2FsbHkpCmxpYnJhcnkocGF0Y2h3b3JrKQoKZGYgPC0gcmVhZF9jc3YoCiAgImh0dHBzOi8vcmF3LmdpdGh1YnVzZXJjb250ZW50LmNvbS9tb3JpbW90b29zYW11L2RhdGFfdmlzdWFsaXphdGlvbi9tYWluL2RhdGEvZGZfNDM0LmNzdiIKICApCgojIOS4u+aIkOWIhuWIhuaekO+8iOaomea6luWMlu+8iQpwY2FfcmVzdWx0IDwtIHByY29tcChkZikjLCBzY2FsZS4gPSBUUlVFKQpwY2FfaW1wb3J0YW5jZSA8LSBhcy5kYXRhLmZyYW1lKHN1bW1hcnkocGNhX3Jlc3VsdCkkaW1wb3J0YW5jZVsyLF0pIHw+CiAgcm93bmFtZXNfdG9fY29sdW1uKCkKbmFtZXMocGNhX2ltcG9ydGFuY2UpIDwtIGMoInBjIiwgInZhbHVlIikKCiMgU3BlY3RyYWwgQ2x1c3RlcmluZwpjbHVzdGVyc19wY2EgPC0gc2ttZWFucyhwY2FfcmVzdWx0JHhbLCAxOjJdLCAzKQoKcDEgPC0gZGF0YS5mcmFtZSgKICBwYzEgPSBwY2FfcmVzdWx0JHhbLCAxXSwKICBwYzIgPSBwY2FfcmVzdWx0JHhbLCAyXSwKICBjbGFzcyA9IGZhY3RvcihjbHVzdGVyc19wY2EkY2x1c3RlcikKICAgICkgfD4KICBnZ3Bsb3QoYWVzKHggPSBwYzEsIHkgPSBwYzIsIGNvbG9yID0gY2xhc3MpKSArCiAgZ2VvbV9wb2ludCgpICsKICBsYWJzKHRpdGxlID0gIuS6jOOBpOOBruS4u+aIkOWIhuOBp+imi+OCiyIpKwogIHRoZW1lKGxlZ2VuZC5wb3NpdGlvbj0ibm9uZSIsIGFzcGVjdC5yYXRpbyA9IDEpCgpwMiA8LSBwY2FfaW1wb3J0YW5jZSB8PgogIGdncGxvdChhZXMoeCA9IHJlb3JkZXIocGMsIGRlc2ModmFsdWUpKSwgeSA9IHZhbHVlKSkgKwogIGdlb21fY29sKCkrCiAgbGFicyh0aXRsZSA9ICLlkITkuLvmiJDliIbjga7jg4fjg7zjgr/mgqbmmI7lipsiLCB4ID0gIiIsIHkgPSAiIikrCiAgdGhlbWUoYXNwZWN0LnJhdGlvID0gMSkKCnAxICsgcDIKYGBgCgojIyMgNC4zLjYg55S75YOP44OH44O844K/44Gu5qyh5YWD5YmK5ribCgpgYGB7ciBtZXNzYWdlPUZBTFNFLCB3YXJuaW5nPUZBTFNFLCBjYWNoZSA9IFRSVUV9CmxpYnJhcnkoY29uZmxpY3RlZCkKbGlicmFyeSh0aWR5dmVyc2UpCmxpYnJhcnkoTUFTUykgIyBNRFMoc2FtbW9uKQpsaWJyYXJ5KFJ0c25lKSAjIHQtU05FCmxpYnJhcnkodW1hcCkgIyBVTUFQCgpkZiA8LSByZWFkX2NzdigKICAiaHR0cHM6Ly9yYXcuZ2l0aHVidXNlcmNvbnRlbnQuY29tL21vcmltb3Rvb3NhbXUvZGF0YV92aXN1YWxpemF0aW9uL21haW4vZGF0YS9kaWdpdHMuY3N2IgogICkKCmRmX2NsZWFuZWQgPC0gZGYgfD4KICBkcGx5cjo6c2VsZWN0KCF0YXJnZXQpCgojIOWQhOaJi+azleOBpzLmrKHlhYPjgavlnKfnuK4KIyDkuLvmiJDliIbliIbmnpAKWF9wY2EgPC0gcHJjb21wKGRmX2NsZWFuZWQpJHhbLCAxOjJdCgojIHQtU05FCnNldC5zZWVkKDQyKQpYX3RzbmUgPC0gUnRzbmUoZGZfY2xlYW5lZCwgbnVtX3RocmVhZHMgPSAyKSRZCgojIE1EUwpYX21kcyA8LSBkZl9jbGVhbmVkIHw+CiAgZGlzdCgpIHw+CiAgc2FtbW9uKHRyYWNlID0gRkFMU0UpIHw+CiAgcGx1Y2soInBvaW50cyIpCgojIFVNQVAKc2V0LnNlZWQoNDIpClhfdW1hcCA8LSB1bWFwKGRmX2NsZWFuZWQpJGxheW91dAoKIyBLLW1lYW5zCnNldC5zZWVkKDQyKQpjbHVzdGVyc19wY2EgPC0ga21lYW5zKFhfcGNhLCAxMCkkY2x1c3RlciAgIyBQQ0EKc2V0LnNlZWQoNDIpCmNsdXN0ZXJzX21kcyA8LSBrbWVhbnMoWF9tZHMsIDEwKSRjbHVzdGVyICNNRFMKc2V0LnNlZWQoNDIpCmNsdXN0ZXJzX3RzbmUgPC0ga21lYW5zKFhfdHNuZSwgMTApJGNsdXN0ZXIgIyB0LVNORQpzZXQuc2VlZCg0MikKY2x1c3RlcnNfdW1hcCA8LSBrbWVhbnMoWF91bWFwLCAxMCkkY2x1c3RlciAgIyBVTUFQCgojIOe1kOaenOOCkuODh+ODvOOCv+ODleODrOODvOODoOOBq+OBvuOBqOOCgeOCiwpkZl9iYXNlIDwtIGRhdGEuZnJhbWUoCiAgICB4ID0gYyhYX3BjYVssIDFdLCBYX21kc1ssIDFdLCBYX3RzbmVbLCAxXSwgWF91bWFwWywgMV0pLAogICAgeSA9IGMoWF9wY2FbLCAyXSwgWF9tZHNbLCAyXSwgWF90c25lWywgMl0sIFhfdW1hcFssIDJdKQogICAgKQoKbiA8LSAxNzk3CgpkaW1yZWQgPC0gYmluZF9yb3dzKAogIGRmX2Jhc2UgfD4KICAgIG11dGF0ZSgKICAgICAgbGFiZWwgPSByZXAoZGYkdGFyZ2V0LCA0KSwKICAgICAgbWV0aG9kID0gYyhyZXAoInBjYV9sYWJlbCIsIG4pLCByZXAoIm1kc19sYWJlbCIsIG4pLHJlcCgidHNuZV9sYWJlbCIsIG4pLHJlcCgidW1hcF9sYWJlbCIsIG4pKQogICAgICApLAogIGRmX2Jhc2UgfD4KICAgIG11dGF0ZSgKICAgICAgbGFiZWwgPSBjKGNsdXN0ZXJzX3BjYSwgY2x1c3RlcnNfbWRzLCBjbHVzdGVyc190c25lLCBjbHVzdGVyc191bWFwKSwKICAgICAgbWV0aG9kID0gYyhyZXAoInBjYV9rbWVhbnMiLCBuKSwgcmVwKCJtZHNfa21lYW5zIiwgbikscmVwKCJ0c25lX2ttZWFucyIsIG4pLHJlcCgidW1hcF9rbWVhbnMiLCBuKSkKICAgICAgKQopIHw+CiAgbXV0YXRlKAogICAgbWV0aG9kID0gZmFjdG9yKAogICAgICBtZXRob2QsCiAgICAgIGxldmVscyA9IGMoInBjYV9rbWVhbnMiLCAicGNhX2xhYmVsIiwgIm1kc19rbWVhbnMiLCAibWRzX2xhYmVsIiwKICAgICAgICAgICAgICAgICAidHNuZV9rbWVhbnMiLCAgInRzbmVfbGFiZWwiLCAidW1hcF9rbWVhbnMiLCAidW1hcF9sYWJlbCIpKSwKICAgIGxhYmVsID0gZmFjdG9yKGxhYmVsKQogICAgKQoKIyDjgq/jg6njgrnjgr/jg6rjg7PjgrDntZDmnpzjgajmraPop6Pjg6njg5njg6vjga7mj4/nlLsKZGltcmVkIHw+CiAgZ2dwbG90KGFlcyh4ID0geCwgeSA9IHksIGNvbG9yID0gbGFiZWwpKSArIAogIGdlb21fcG9pbnQoKSArIAogIGxhYnModGl0bGU9IuanmOOAheOBquasoeWFg+Wcp+e4ruaWueazlSIpICsKICB0aGVtZSgKICAgIGF4aXMudGlja3MgPSBlbGVtZW50X2JsYW5rKCksICAjIHRpY2vjga7nt5rjgpLmtojjgZkKICAgIGF4aXMudGV4dCA9IGVsZW1lbnRfYmxhbmsoKSwgICAjIHRpY2vjga7mlbDlrZfjgpLmtojjgZkKICAgIGF4aXMudGl0bGUgPSBlbGVtZW50X2JsYW5rKCksICAjIOi7uOOBruODqeODmeODq+OCkua2iOOBmQogICAgYXhpcy5saW5lID0gZWxlbWVudF9ibGFuaygpLCAgICMg6Lu444Gu57ea44KS5raI44GZCiAgICBsZWdlbmQucG9zaXRpb249Im5vbmUiLAogICAgYXNwZWN0LnJhdGlvID0gMQogICkgKwogIGZhY2V0X3dyYXAodmFycyhtZXRob2QpLCBucm93ID0gMiwgc2NhbGVzID0gImZyZWUiKQpgYGAKCuesrDTnq6Djga/jgZPjgZPjgb7jgafjgIIK